1. (和)最大子序列(連續(xù))
這是一道非常經(jīng)典的動態(tài)規(guī)劃的題目，用到的思路我們在別的動態(tài)規(guī)劃題目中也很常用包吝，以后我們稱為”局部最優(yōu)和全局最優(yōu)解法“饼煞。基本思路是這樣的诗越，在每一步砖瞧，我們維護(hù)兩個變量，一個是全局最優(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步的表達(dá)式是：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]是負(fù)的宏娄，那么加上他就不如不需要的问裕，所以不然就是直接用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);
}
};
2. 最長遞增子序列(不連續(xù)) LIS
一個簡單的思路漂问，O(n^2)赖瞒。編程之美里的一個思路可以加速到O(nlgn)
一個整型數(shù)組，求其中最長遞增子序列的長度蚤假。
簡單的想法：從前到后遍歷數(shù)組栏饮，對于每一個元素，從該元素開始往前判斷是不是大于前面的元素磷仰，如果大于袍嬉，則根據(jù)是否大于當(dāng)前位置的最長子序列長度，相應(yīng)的更新當(dāng)前這個子序列的長度灶平。
public class CopyOfTest1 {
public static void main(String ss[]) {
System.out.println(get(new int[] { 1, -1, 2, -3, 4, -5, 6, -7 }));
}
public static int get(int[] data) {
int[] len = new int[data.length];// 記錄最長信息
for (int i = 0; i < len.length; i++) {
len[i] = 1;
}
for (int i = 0; i < data.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (data[i] > data[j] && len[i] < len[j] + 1) {
len[i] = len[j] + 1;
}
}
}
int max = -1;
for (int i = 0; i < len.length; i++) {
if (max < len[i]) {
max = len[i];
}
}
return max;
}
}
