這是一道非常經(jīng)典的動態(tài)規(guī)劃的題目，用到的思路我們在別的動態(tài)規(guī)劃題目中也很常用锌仅，以后我們稱為”局部最優(yōu)和全局最優(yōu)解法“章钾。基本思路是這樣的热芹，在每一步贱傀，我們維護兩個變量，一個是全局最優(yōu)伊脓，就是到當(dāng)前元素為止最優(yōu)的解是府寒，一個是局部最優(yōu)，就是必須包含當(dāng)前元素的最優(yōu)的解。接下來說說動態(tài)規(guī)劃的遞推式（這是動態(tài)規(guī)劃最重要的步驟株搔，遞歸式出來了剖淀，基本上代碼框架也就出來了）。假設(shè)我們已知第i步的global[i]（全局最優(yōu)）和local[i]（局部最優(yōu)）纤房，那么第i+1步的表達式是：local[i+1]=Math.max(A[i], local[i]+A[i])纵隔，就是局部最優(yōu)是一定要包含當(dāng)前元素，所以不然就是上一步的局部最優(yōu)local[i]+當(dāng)前元素A[i]（因為local[i]一定包含第i個元素帆卓，所以不違反條件）巨朦，但是如果local[i]是負的，那么加上他就不如不需要的剑令，所以不然就是直接用A[i]糊啡；
局部最優(yōu)和全局最優(yōu)解法
- 首先local[i]表示以a[i]為結(jié)尾的子序列的最大的和，則global = max{local[0], ... , local[n-1]} 吁津。 global即為答案棚蓄。而local[i + 1]只有兩個選擇，要不就是和之前的數(shù)字連在一起組成一個序列碍脏，或者自己a[i+1]獨立組成一個序列梭依，哪個大選哪個,local[i+1] = max{ a[i+1], local[i] + a[i+1] }.
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
#include <string>
#include <set>
using namespace std;
class Solution {
private:
int max(int a, int b)
{
return a>b? a:b;
}
public:
int maxSubArray(vector<int>& nums) {
int size = (int)nums.size();
int local = nums[0];
int global = local;
for (int i = 1; i < size; i++)
{
local = max(local + nums[i], nums[i]);
global = max(local, global);
}
return global;
}
};
分治法
易知，對于一數(shù)字序列典尾，其最大連續(xù)子序列和對應(yīng)的子序列可能出現(xiàn)在三個地方役拴。或是整個出現(xiàn)在輸入數(shù)據(jù)的前半部（左）钾埂，或是整個出現(xiàn)在輸入數(shù)據(jù)的后半部（右）河闰，或是跨越輸入數(shù)據(jù)的中部從而占據(jù)左右兩半部分。前兩種情況可以通過遞歸求解褥紫，第三種情況可以通過求出前半部分的最大和（包含前半部分的最后一個元素）以及后半部分的最大和（包含后半部分的第一個元素）而得到姜性，然后將這兩個和加在一起即可。
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
#include <string>
#include <set>
using namespace std;
class Solution {
private:
int max(int a, int b)
{
return a>b? a:b;
}
int maxSubSum(vector<int>& nums, int l, int r)
{
if (l == r) return nums[l];
int mid = (l + r)/2;
int wholeLeft = maxSubSum(nums, l, mid);
int wholeRight = maxSubSum(nums, mid+1, r);
int partleft = nums[mid];
int sum = partleft;
for (int i = mid-1; i>= l; i--)
{
sum += nums[i];
partleft = max(partleft, sum);
}
int partright = nums[mid+1];
int sum2 = partright;
for (int i = mid + 2; i <= r; i++)
{
sum2 += nums[i];
partright = max(partright, sum2);
}
return max(max(wholeRight, wholeLeft), partright + partleft);
}
public:
int maxSubArray(vector<int>& nums) {
int size = (int)nums.size();
return maxSubSum(nums, 0, size-1);
}
};
