力扣原題鏈接，點(diǎn)擊跳轉(zhuǎn)。

請(qǐng)?jiān)谝粋€(gè)數(shù)組nums中找出一個(gè)子數(shù)組，使得這個(gè)子數(shù)組中所有元素的和最大。

你當(dāng)然可以采取暴力枚舉的方法，但是效率太低。這里我們用動(dòng)態(tài)規(guī)劃的思想來解決這個(gè)問題。首先確定狀態(tài)表示：我們用dp[i]表示以i結(jié)尾的所有子數(shù)組的最大和。

接著推導(dǎo)狀態(tài)轉(zhuǎn)移方程。分類討論：

• 如果以i結(jié)尾的子數(shù)組只包含nums[i]，那么和為nums[i]。
• 如果以i結(jié)尾的子數(shù)組長度大于1，那么和為dp[i-1]+nums[i]。

所以，dp[i]=max(nums[i],dp[i-1]+nums[i])。

接著考慮初始化的問題。顯然dp[0]=nums[0]。填表時(shí)應(yīng)按照從左往右的順序。最終應(yīng)返回整個(gè)dp表中的最大值。

class Solution {
public:int maxSubArray(vector<int>& nums) {// 創(chuàng)建dp表int n = nums.size();vector<int> dp(n);// 初始化dp[0] = nums[0];// 從左往右填表for (int i = 1; i < n; i++){dp[i] = max(nums[i], dp[i-1] + nums[i]);}// 返回整個(gè)dp表的最大值return *max_element(dp.begin(), dp.end());}
};

當(dāng)然，你也可以在填表的同時(shí)把最大值求了。

class Solution {
public:int maxSubArray(vector<int>& nums) {// 創(chuàng)建dp表int n = nums.size(), ret = 0;vector<int> dp(n);// 初始化ret = dp[0] = nums[0];// 從左往右填表for (int i = 1; i < n; i++){dp[i] = max(nums[i], dp[i-1] + nums[i]);ret = max(ret, dp[i]);}// 返回整個(gè)dp表的最大值return ret;}
};