53. Maximum Subarray*【力扣】

题意理解

求一个数组的最大子序和，最少包含数组的一个元素。

问题分析

动态规划。

思路1：状态量是前i个数最大的子序和，状态转移方程为:

DP[0] = nusm[0];

DP[i] = max ( DP[i - 1], max (nums[j] + ... + nums[i] ) ), 1 <= j < i < n;

思路2：用累加和来处理，累加和的计算方法是，如果前i-1个数的累加和是正，前i个数的累加和就是前i-1个数的累加和+第i个数；如果前i-1个数的累加和是负，前i个数的累加和就重置为第i个数。如果最大那个累加和就是最大子序和。

其他

思路2是我看过但没记住，现在依然不理解这种处理。mark一下。

链接

int maxSubArray(vector<int>& nums) {
        int res = nums[0];  //设置初始子序和为第一个元素值
        int sum = 0;    //计算和值
        for(int i = 0; i < nums.size(); i++) //遍历数组
        {
            if (sum > 0) //碰到和值大于0  难的是这一步
            {
                sum += nums[i];    //和值继续累加
            }
            else     //和值小于0
                sum = nums[i];    //重置和值
            if (sum > res) res = sum;    // 和值大于当前最大值，更新最大值
        }
        return res;
    }