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;
    }