牛客對應題目鏈接：連續子數組最大和_牛客題霸_牛客網 (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;}
};
)
