題目

---

輸入一個長度為n的整型數組array，數組中的一個或連續多個整數組成一個子數組，子數組最小長度為1。求所有子數組的和的最大值。

數據范圍:1<=n<=2×10⁵ ?100<=a[i]<=100

要求:時間復雜度為 O(n)，空間復雜度為 O(n)

示例1

輸入：
[1,-2,3,10,-4,7,2,-5]
返回值：
18
說明：
經分析可知，輸入數組的子數組[3,10,-4,7,2]可以求得最大和為18

示例2

輸入：
[2]
返回值：
2

思路

---

這題屬于動態規劃，可以使用狀態轉移方程求得子數組的最大值。

• 用dp數組表示以下標i為終點的最大連續子數組和。
• 遍歷數組，每次遇到一個新的數組元素，連續的子數組要么加上變得更大，要么這個元素本身就更大，就可以舍棄之前的子數組。狀態轉移方程為dp[i]=max(dp[i?1]+array[i],array[i])。
• 維護一個最大值記錄當前已經得到的最大和的值。

解答代碼

---

#include <algorithm>
#include <vector>
class Solution {
public:/*** @param array int整型vector * @return int整型*/int FindGreatestSumOfSubArray(vector<int>& array) {// write code hereif (array.empty()) {return 0;}auto size = array.size();vector<int> dp(size, 0);dp[0] = array[0];int max_sum = dp[0];for (int i = 1; i < size; i++) {//狀態轉移方程dp[i] = max(dp[i-1] + array[i], array[i]);//記錄最大值max_sum = max(dp[i], max_sum);}return max_sum;}
};