設(shè)長度為N的數(shù)組為{a0，a1, a2, ...an-1)焙畔，則假定以aj結(jié)尾的數(shù)組序列的最長遞增子序列長度為L(j)，則L(j)={ max(L(i))+1, i<j且a[i]<a[j] }挺物。也就是說豪椿，我們需要遍歷在j之前的所有位置i(從0到j(luò)-1)，找出滿足條件a[i]<a[j]的L(i)叨恨，求出max(L(i))+1即為L(j)的值柳刮。最后，我們遍歷所有的L(j)（從0到N-1）特碳，找出最大值即為最大遞增子序列诚亚。時(shí)間復(fù)雜度為O(N^2)。

例如給定的數(shù)組為{5午乓，6站宗，7，1益愈，2梢灭，8}，則L(0)=1, L(1)=2, L(2)=3, L(3)=1, L(4)=2, L(5)=4蒸其。所以該數(shù)組最長遞增子序列長度為4敏释，序列為{5，6摸袁，7钥顽，8}。算法代碼如下：

1. #include???

2. using?namespace?std;??

3. #define?len(a)?(sizeof(a)?/?sizeof(a[0]))?//數(shù)組長度??

4. int?lis(int?arr[],?int?len)??

5. {

6. int?longest[len];??

7. for?(int?i=0;?i<len;?i++)??

8. longest[i]?=?1;

9.

10. for?(int?j=1;?j<len;?j++)?{??

11. for?(int?i=0;?i<j;?i++)?{??

12. if?(arr[j]>arr[i]?&&?longest[j]<longest[i]+1){?//注意longest[j]<longest[i]+1這個(gè)條件靠汁，不能省略蜂大。??

13. longest[j]?=?longest[i]?+?1;//計(jì)算以arr[j]結(jié)尾的序列的最長遞增子序列長度??

14. }

15. }

16. }

17.

18. int?max?=?0;??

19. for?(int?j=0;?j<len;?j++)?{??

20. cout?<<"longest["?<<?j?<<?"]="?<<?longest[j]?<<?endl;??

21. if?(longest[j]?>?max)?max?=?longest[j];??//從longest[j]中找出最大值??

22. }

23. return?max;??

24. }

1. int?main()??

2. {

3. int?arr[]?=?{1,?4,?5,?6,?2,?3,?8};?//測(cè)試數(shù)組??

4. int?ret?=?lis(arr,?len(arr));??

5. ????cout?<<?"max?increment?substring?len="?<<?ret?<<?endl;??

6. ????return?0;??

7. }

算法思想總結(jié)：

例如給定的數(shù)組為{5，6蝶怔，7奶浦，1，2踢星，8}澳叉，則L(0)=1, L(1)=2, L(2)=3, L(3)=1, L(4)=2, L(5)=4。所以該數(shù)組最長遞增子序列長度為4沐悦，序列為{5成洗，6，7藏否，8}

什么意思呢泌枪？

對(duì)于這個(gè)數(shù)組{5，6秕岛，7碌燕，1误证，2，8}修壕，假設(shè)它的下標(biāo)為i的時(shí)候愈捅，它的最長遞增序列長度為length

s->對(duì)應(yīng)元素組元素

L->對(duì)應(yīng)最長遞增序列

那么L(0) ->s{5}->L{5}->1

L(1) ->s{5,6}->L{5,6}->2

L(2) ->s{5,6,7}->L{5,6,7}->3

L(3) ->s{5,6,7,1}->L{1}->1

L(4) ->s{5,6,7,1,2}->L{1,2}->2

L(5) ->s{5,6,7,1,2,8}->L{5,6,7,8}->5

上面得L(5) = L{5,6,7,8} = {5,6,7} + 8 = L(2) + 1

所以L(5)可能是L(4) + 1或者L(3) + 1 或者L(2) + 1或者L(1) + 1或者L(0) + 1，前提a[5] > a[4]或者a[3]或者a[2]或者a[1]或者a[0]

所以這個(gè)例子只是一種情況慈鸠，所以對(duì)于L(i)蓝谨，他可能是L(0)+1,L(1)+1…L(i-1)+1轉(zhuǎn)移過來的但是很幸運(yùn)的是動(dòng)態(tài)規(guī)劃算法把L(0)，L(1)青团，L(2)….L(i-1)都保存下來了（所以DP當(dāng)問題復(fù)雜度解到第i步的時(shí)候譬巫，前面所有可能問題的解L(0),L(1),L(2),,,,L(i-1)都保存下來了，這也是它的關(guān)鍵督笆，而DP本身就是求的所有子問題的解L(0),L(1),L(2),,,,L(n)芦昔，然后找出所有解最大的那個(gè)），前面必須滿足條件a[i] > a[j]

如果a[i] < a[j]則不管

注意：最后不一定是L(5)最大（你可以看下L(4) ->s{5,6,7,1,2}->L{1,2}->2娃肿，只有兩個(gè)

）咕缎，如果上面的條件不滿足的話或者a[5]比較小的話，那就是L(2)最大料扰，所以最終還會(huì)遍歷一遍L數(shù)組凭豪，尋找最大的那個(gè)，任何一個(gè)下標(biāo)對(duì)應(yīng)的都可能最大

還有一點(diǎn)注意：上面的longest[j]<longest[i]+1也很重要晒杈，表示如果滿足a[i] > a[j]并且加了一個(gè)a[j]后嫂伞，它的個(gè)數(shù)比原來的longest[j]要大，就賦值拯钻，這個(gè)為什么能起作用帖努，就是由于初始條件longest[j]全都被初始化為了1，所以這個(gè)很關(guān)鍵

總結(jié)：

所以DP當(dāng)問題復(fù)雜度解到第i步的時(shí)候说庭，前面所有可能問題的解L(0),L(1),L(2),,,,L(i-1)都保存下來了然磷，這也是它的關(guān)鍵郑趁，而DP本身就是求的所有子問題的解L(0),L(1),L(2),,,,L(n)刊驴，然后找出所有解最大的那個(gè)，針對(duì)這個(gè)例子找的是最大那個(gè)