動態規劃之最長單調遞增子序列（C++源碼）

動態規劃之最長單調遞增子序列

問題：

L={a1,a2,a3,…,an}既L是由n個不同的實數組成的序列，求L的最長單調遞增子序列（下標可不連續）。

分析：

設輔助數組b，b[i]表示以a[i]為結尾的最長遞增子序列的長度，最長遞增子序列的長度，就是數組b的最大值。

代碼：

最優值：

#include<bits/stdc++.h>

using namespace std;

#define num 100

int a[num];

int LMax(int n){

int b[num]={0};

b[1]=1;//數組只有一個數時，最長為1

int max=0；

for(int i=2;i<=n;i++){

int k=0;

for(int j=1;j<i;j++){

if(a[j]<=a[i]&&k<b[j]){

k=b[j];

b[i]=k+1;

}

if(max<b[i]){

max=b[i];

}

}

}

return max;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

主函數：

int main(){

int n;

cin>>n;

for(int i=1;i<=n;i++){

cin>>a[i];

}

cout<<LMax(n)<<endl;

}

1

2

3

4

5

6

7

8

測試：

打開今日頭條，查看更多精彩圖片

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！