Java教程

动态规划——剑指 Offer 42. 连续子数组的最大和

本文主要是介绍动态规划——剑指 Offer 42. 连续子数组的最大和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

动态规划——剑指 Offer 42. 连续子数组的最大和

题目：

思路：

  1. dp数组的定义：dp[i]是以 nums[i] 结尾的最大子数组和。
  2. base_case：dp[0] = nums[0]
  3. 状态转移方程:dp[i]有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);

代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int min = INT_MIN;
        vector<int> dp(n+1, INT_MIN);

        dp[0] = nums[0];

        for(int i = 1; i<n;i++){
            dp[i] = max(nums[i], nums[i] + dp[i-1]);
        }

        return *max_element(dp.begin(),dp.end());

    }
};

Rank：

Tips：

这篇关于动态规划——剑指 Offer 42. 连续子数组的最大和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航