1570: Sequence Number
时间限制: 1 Sec 内存限制: 1280 MB
题目描述
In Linear algebra, we have learned the definition of inversion number:
Assuming A is a ordered set with n numbers ( n > 1 ) which are different from each other. If exist positive integers i , j, ( 1 ≤ i < j ≤ n and A[i] > A[j]), <A[i], A[j]> is regarded as one of A’s inversions. The number of inversions is regarded as inversion number. Such as, inversions of array <2,3,8,6,1> are <2,1>, <3,1>, <8,1>, <8,6>, <6,1>,and the inversion number is 5.
Similarly, we define a new notion —— sequence number, If exist positive integers i, j, ( 1 ≤ i ≤ j ≤ n and A[i] <= A[j], <A[i], A[j]> is regarded as one of A’s sequence pair. The number of sequence pairs is regarded as sequence number. Define j – i as the length of the sequence pair.
Now, we wonder that the largest length S of all sequence pairs for a given array A.
输入
There are multiply test cases.
In each case, the first line is a number N(1<=N<=50000 ), indicates the size of the array, the 2th ~n+1th line are one number per line, indicates the element Ai (1<=Ai<=10^9) of the array.
输出
Output the answer S in one line for each case.
样例输入
5 2 3 8 6 1
样例输出
3
解题思路
求出当A[i]<=A[j],i<=j时,j-i的最大长度。
#include <stdio.h> #include <algorithm> using namespace std; int a[50010]; int main () { int n, i, j, k, maxn; while (~scanf("%d",&n)) { for (i = 0; i < n; i++) scanf("%d", &a[i]); for (i = n - 1; i >= 0 && a[i] < a[0]; i--); maxn = i; for (j = 1; j < n - maxn; j++) { for (k = n - 1; k >= j + maxn; k--) { if (a[j] <= a[k]) { maxn = max(maxn, k - j); break; } } } printf("%d\n", maxn); } return 0; }