牛客对应题目链接：连续子数组最大和_牛客题霸_牛客网 (nowcoder.com)

力扣对应题目链接：53. 最大子数组和 - 力扣（LeetCode）

核心考点 ：简单动归问题。

---

一、《剑指Offer》对应内容

---

二、分析题目

1、贪心

从前往后迭代，一个个数字加过去，如果 sum<res，则重新开始找子序串。

---

2、动态规划

• 定义状态 dp[i]：表示以 i 下标结尾的最大连续子序列的和。
• 状态递推：dp[i] = max(dp[i-1]+array[i], array[i]) 【 注意：这里一定要连续关键字】
• 状态的初始化：dp[0] = array[0], max = array[0]

很明显，上面的这个做法只会使用到 dp[i] 和 dp[i-1]，所以是有优化的可能的。

---

三、代码

//牛客
#include <iostream>
using namespace std;

const int N=2e5+10;
int arr[N], dp[N];

int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    dp[0]=arr[0];
    int res=arr[0];
    for(int i=1; i<n; i++)
    {
        dp[i]=max(dp[i-1]+arr[i], arr[i]);
        res=max(res, dp[i]);
    }
    cout << res << endl;
    return 0;
}

//基于上面代码的优化
#include <iostream>
using namespace std;

const int N=2e5+10;
int arr[N];

int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++) cin >> arr[i];
    int sum=arr[0];
    int res=arr[0];
    for(int i=1; i<n; i++)
    {
        if(sum>=0) sum+=arr[i];
        else sum=arr[i];
        res=max(res, sum);
    }
    cout << res << endl;
    return 0;
}

//力扣
//方法一
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res=-2e4;
        int sum=0;
        for(int i=0; i<nums.size(); i++)
        {
            sum+=nums[i];
            if(sum>res)
                res=sum;
            if(sum<0)
                sum=0;
        }
        return res;
    }
};

//方法二(与上面牛客的写法不太一样)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n+1);
        int res=-2e4;
        for(int i=1; i<=n; i++)
        {
            dp[i]=max(nums[i-1], dp[i-1]+nums[i-1]);
            if(dp[i]>res) res=dp[i];
        }
        return res;
    }
};