课程笔记：程序设计与算法（二）算法基础：dp

Longest Ordered Subsequence

Time Limit: 2000MS Memory Limit: 65536K
Description
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
Input
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000
Output
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input
7
1 7 3 5 9 4 8
Sample Output
4

题目描述

解题步骤

1.找子问题

• “求序列的前n个元素的最长上升子序列的长度”是个子问题。
  但是这样分解子问题，不具有“无后效性”。

  假设F(n) = x,但可能有多个序列满足F(n) = x 。有的序列的最后一个元素比小，则加上就能形成更长上升子序；有的序列最后一个元素不比小……以后的事情受到如何达到状态n的影响，不符合“无后效性”。

• 一个好的子问题：“求以(k=1,2,3…N)为终点的最长上升子序列”

  一个上升子序列中最右边的那个数，称为该子序列的“终点”。

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

2. 确定状态

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

3. 找出状态转移方程

   • maxLen（x）表示以做为“终点”的最长上升子序列的长度那么：

   初始状态：maxLen(1) = 1
   maxLen(k) = max {maxLen (i) :1<=i<k且<且k1} + 1
   maxLen(k)的值，就是在左边，“终点”数值小于,且上都最大的那个上升子序列的长度再加1。因为左边任何“终点”小于的子序列，加上后就能形成一个更长的上升子序列。

时间时间复杂度:状态的数目*找到状态所花的时间：N个状态*N，所以复杂度为O()

代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100;
int maxLen[MAXN];
int a[MAXN];
int main(){
    int N;
    cin>>N;
    for(int i = 0; i<N ;i++){
        cin>>a[i];
        maxLen[i] = 1;
    }
    for(int i = 1 ;i<N ;i++){
//每次求第a[i]个为终点的lis的长度
        for(int j = 0 ; j<i;j++){
//查看以a[j]为终点的的lis
            if(a[j]<=a[i]){
                maxLen[i] = max(maxLen[i],maxLen[j]+1);
            }
        }
    } //复杂度为O(n*n)
    cout<< * max_element(maxLen,maxLen + N);
    return 0; 
} 

STL之min_element()与max_element