一、題目解析

在給定順序的數組中找出一段具有最大和的連續子數組，且大小最小為1.

二、算法原理

1.狀態表示

?

我們可以意一一枚舉出所有的子數組，但我們想要的是最大子數組，所以f[i]表示：以i位置為結尾，所有子數組的最大和

2.狀態轉移方程

?

f[i]當長度為1時，此時的子數組和為nums[i]，當長度大于1時，此時的子數組和為[0,i-1]的子數組最大值加上nums[i]，我們需要取二者中的最大值。

所以f[i]=max(nums[i],f[i-1]+nums[i]);

3.初始化

在計算f[i]中我們用到了f[i-1]當i處于0位置時，越界訪問，所以我們可以直接初始化f[0]，或者加一個虛擬格子用于初始化。

?

4.填表順序

從左到右填表，保證所需值已計算

5.返回值

由于f[i]中存儲的是到達i位置的最大子數組和，我們需要知道從[0,n-1]?區間內的最大值，所以返回值為f[i]中的最大值

思考與實踐同等重要，在思考后可以去實現一下，鏈接：53. 最大子數組和 - 力扣（LeetCode）

?三、代碼示例

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();vector<int> dp(n+1);for(int i = 1;i<=n;i++){dp[i] = max(nums[i-1],dp[i-1]+nums[i-1]);}int MAX = INT_MIN;//數組中存在負數，所以在比大小時用int的最小值比較，也可以賦值f[1]從2到n開始比較for(int i = 1;i<=n;i++){if(dp[i]>MAX) MAX = dp[i];}return MAX;}
};

?

看到最后，如果對您有所幫助請點贊、收藏和關注，?點點關注不迷路，我們下期再見！