题目链接:http://codeforces.com/problemset/problem/702/A
题意:
给你N个数,a[0], a[1], a[2], ....., a[n-1],让你找出最长的连续上升子序列中元素的个数。
思路:
设dp[i]代表以a[i]结尾的连续上升子序列中元素的个数,那么dp[i] = (a[i] > a[i - 1] ? dp[i - 1] + 1 : 1),含义是如果a[i]比a[i-1]大,那么a[i]可以加入到以a[i-1]为尾的最长连续上升子序列末尾,取代a[i-1]成为新的末尾,原本的长度加1。否则a[i]单独作为一个子序列,长度为1。然后找到这个数组的最大值就OK了。实现时,可以用一个滚动变量来代替这个数组,优化空间复杂度。
代码:
1 #include <iostream> 2 #include <cmath> 3 #include <cstdio> 4 #include <cstring> 5 #include <cstdlib> 6 #include <stack> 7 #include <queue> 8 #include <vector> 9 #include <algorithm> 10 #include <string> 11 12 typedef long long LL; 13 using namespace std; 14 15 int main() { 16 int n, ans = -1, cnt = 1, a, b; 17 scanf("%d%d", &n, &a); 18 for(int i = 1; i < n; i++) { 19 scanf("%d", &b); 20 b > a ? cnt++ : (ans = ( cnt > ans ? cnt : ans) , cnt = 1); 21 a = b; 22 } 23 printf("%d ", cnt > ans ? cnt : ans); 24 return 0; 25 }