題目鏈接：點(diǎn)擊這里

1.動(dòng)態(tài)規(guī)劃

令狀態(tài) 表示以 作為末尾的連續(xù)序列的最大和（即 必須作為連續(xù)序列的末尾）

通過(guò)這個(gè) 數(shù)組资昧，要求的最大子序和其實(shí)就是 中的最大值。

現(xiàn)作如下考慮：因?yàn)? 要求是必須以 結(jié)尾的連續(xù)序列，那么只有兩種情況：

1. 這個(gè)最大和的連續(xù)序列只有一個(gè)元素朴肺，即以 開(kāi)始，以 結(jié)尾坚洽。
2. 這個(gè)最大和的連續(xù)序列有多個(gè)元素戈稿，即從前面某處 開(kāi)始 ，一直到 結(jié)尾讶舰。

對(duì)第1種情況鞍盗，最大和就是 本身。

對(duì)第2種情況跳昼，最大和是 橡疼，即 。

于是得到狀態(tài)轉(zhuǎn)移方程：庐舟，其中

時(shí)間復(fù)雜度為 ，空間復(fù)雜度為

AC代碼：

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

        dp[0] = nums[0];
        for(int i = 1; i < n; i++)
        {
            if(dp[i - 1] > 0)   dp[i] = dp[i - 1] + nums[i];
            else    dp[i] = nums[i];
        }
        
        // dp[i]存放以nums[i]結(jié)尾的連續(xù)序列的最大和住拭，需要遍歷得到最大的才是結(jié)果
        int ans = INT_MIN;
        for(int i = 0; i < n; i++)
            if(dp[i] > ans)
                ans = dp[i];

        return ans;
    }
};

/* 和上面思路完全一致挪略，代碼更加簡(jiǎn)潔：
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);

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

        return ans;
    }
};
*/

空間優(yōu)化：我們只需要一個(gè)變量 premax 保存前一個(gè)狀態(tài)的最大值，另需一個(gè)變量 ans 保存全局最大值滔岳。

時(shí)間復(fù)雜度為 杠娱，空間復(fù)雜度為

AC代碼：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        int premax = nums[0];
        int ans = nums[0];
        for(int i = 1; i < n; i++)
        {
            if(premax > 0)  premax = premax + nums[i];
            else    premax = nums[i];
            ans = max(ans, premax);
        }

        return ans;
    }
};

2.分治

最大連續(xù)子序列和主要由以下三部分子區(qū)間里元素的最大和，對(duì)它們?nèi)咔笞畲笾导纯伞?/p>

image.png

由遞歸主定理 谱煤，解出總時(shí)間復(fù)雜度為 摊求。

需要額外 的空間用于遞歸的系統(tǒng)棧。

class Solution {
public:
    int calc(int l, int r, vector<int>& nums)
    {
        if(l == r)  return nums[l];

        int mid = (l + r) >> 1;

        int left = calc(l, mid, nums);
        int right = calc(mid + 1, r, nums);

        int lmax = nums[mid], lsum = 0;
        for(int i = mid; i >= l; i--)
        {
            lsum += nums[i];
            lmax = max(lmax, lsum);
        }

        int rmax = nums[mid + 1], rsum = 0;
        for(int i = mid + 1; i <= r; i++)
        {
            rsum += nums[i];
            rmax = max(rmax, rsum);
        }

        return max(max(left, right), lmax + rmax);
    }

    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        return calc(0, n - 1, nums);
    }
};