JiaHeng-DLUT
8/6/2019 - 8:38 AM

Longest Increasing Subsequence

最长不下降子序列

Q

在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的。

Sample Input:
7
1 2 3 -1 -2 7 9
Sample Output:
5 (1 2 3 7 9)

A

  • dp[i] : 以 A[i] 结尾的最长不下降子序列的长度
  • return *max_element(dp, dp + n);
  • dp[i] = max{ 1, dp[j] + 1 }, j = 1,2,...,i-1 && A[j] < A[i]
  • dp[i] = 1, 1 <= i <= n
  • O(n^2)
1 2 3  4  5 6 7
1 2 3 -1 -2 7 9

dp[1] = 1
dp[2] = max{ 1, dp[1] + 1 } = max{ 1, 2 } = 2
dp[3] = max{ 1, dp[1] + 1, dp[2] + 1 } = max{ 1, 2, 3 } = 3
dp[4] = 1
dp[5] = 1
dp[6] = max{ 1, dp[1] + 1, dp[2] + 1, dp[3] + 1, dp[4] + 1, dp[5] + 1 }
      = max{ 1, 2, 3, 4, 1, 1} = 4
dp[7] = max{ 1, dp[1] + 1, dp[2] + 1, dp[3] + 1, dp[4] + 1, dp[5] + 1, dp[6] + 1 }
      = max{ 1, 2, 3, 4, 1, 1, 5} = 5
LIS.cpp
content_copyfile_download
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100;
int A[N], dp[N];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
	}
	int ans = -1;	// Record the maximum of dp[i]
	for (int i = 1; i <= n; i++) {	// calculate dp[i] in order
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (A[i] >= A[j] && (dp[j] + 1 > dp[i])) {
				dp[i] = dp[j] + 1;	// state transition equation, used to update dp[i] 
			}
		}
		ans = max(ans, dp[i]);
	}
	cout << ans << endl;
	return 0;
}

/*
Sample Input:
8 
1 2 3 -9 3 9 0 11 
Sample Output:
6 // 1 2 3 3 9 11
*/