最长上升子序列

C++ STL 求向量中的最大值和最小值min_element(v.begin(),v.end())
max_element(v.begin(),v.end()) sizeof(n)/sizeof(int) min_element
算法返回最小的元素的位置中序列 [first, last)。

问题描述

一个数的序列ai，当a 1 < a 2 < … < a S 的时候，我们称这个序列是上升的。对于给定的一个序列(a 1 , a 2 ,
…, a N )，我们可 以得到一些上升的子序列(a i1 , a i2 , …, a iK )，这里1 <= i1

“求以a k （k=1, 2, 3…N）为终点的最长上升子序列的长度”一个上升子序列中最右边的那个数，称为该子序列的“终点”。

**
虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。

2. 确定状态：
子问题只和一个变量– 数字的位置相关。因此序列中数的位置k 就是“状态”，而状态 k 对应的“值”，就是以a k做为“终点”的最长上升子序列的长度。状态一共有N个。

3. 找出状态转移方程：
maxLen (k)表示以a k 做为“终点”的最长上升子序列的长度那么：初始状态：

maxLen (1) = 1 
maxLen (k) = max { maxLen (i)：1<=i < k 且 a i < a k 且 k≠1 } + 1

   

  

   
1
   
2
  

若找不到这样的i,则maxLen(k) = 1 maxLen(k)的值，就是在a k 左边，“终点”数值小于a k ，且长度最大的那个上升子序列的长度再加1。因为a k 左边任何“终点”小于a k 的子序列，加上a k 后就能形成一个更长的上升子序列。

“人人为我”递推型动归程序

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 1010
using namespace std;
int a[MAX], maxLen[MAX];

int main()
{
    int N;
    cin >> N;
    for(int i=1; i<=N; i++)
    {
        cin >> a[i];
        maxLen[i] = 1;
    }
    for(int i=2; i<=N; i++)
    {
        for(int j=1; j<i; j++)
        {
            if(a[i] > a[j])
                maxLen[i] = max(maxLen[i], maxLen[j]+1);//注意这里要取maxLen[i] 和 maxLen[j]+1的最大值 如果不是这样，见图片后果
        }
    }
    cout << *max_element(maxLen+1, maxLen+N+1);
    return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

对应51NOD 1134

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 50010

int A[N];
int B[N];

int Upper_bound(int len, int A)
{
    int i;
    for(i=0; i<len; i++)
    {
        if(B[i] > A)
            return i;
    }
    return i;
}
int List(int n)
{
    B[0] = A[0];
    int len =1;
    for(int i=1; i<n; i++)
    {
        B[ A[i]>B[len-1]? len++:Upper_bound(len, A[i]) ] = A[i];
    }
    return len;
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", &A[i]);
    printf("%d", List(n));
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

C++有类似STL

lower_bound(first, last, val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

upper_bound(first, last, val)算法返回一个非递减序列[first, last)中第一个大于val的位置。

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/61629640