Can anybody provide me a hint for this problem. I am not able to get what the dp states should be.

Thanks in advance.

Recently solved a problem from round #61 Div 2(http://mirror.codeforces.com/problemset/problem/66/B) in O(n) complexity using DP. I guess i found a better solution than the one given in the editorial(with O(n^2) complexity).

My solution:
1. for all 1<=i<=n,a[i][0] state represents length of longest contiguous increasing subsequence ending at i
2. for all 1<=i<=n, a[i][1] state represents length of longest contiguous decreasing subsequence starting at i
3. for the solution find the maximum among all (a[i][0] + a[i][1] -1 ) for all i from 1 to n

I did this because for the problem it was required to find a block, before and after which maximum number of blocks were decreasing in height continuously.
For the example where n = 5 and the heights were 4 2 3 3 2, for the first three, a[3][0] = 2 and a[3][1] = 3 and for the second three, a[4][0] = 3 and a[4][1] = 2. The value of a[3][0] + a[3][1] -1 and a[4][0] + a[4][1] -1 was 4 which was the maximum so any of the two positions could be selected.

My Code:

#include <stdio.h>

#define inc 0
#define dec 1

#define max(a,b) (a>b?(a):(b))

int h[1001];
int a[1001][2];

int main(){
    int n,i,answer;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&h[i]);
    a[1][inc] = 1;
    for(i=2;i<=n;i++){
        if(h[i]>=h[i-1])
            a[i][inc] = 1 + a[i-1][inc];
        else
            a[i][inc] = 1;            
    }
    a[n][dec] = 1;
    for(i=n-1;i>=1;i--){
        if(h[i]>=h[i+1])
            a[i][dec] = a[i+1][dec] + 1;
        else
            a[i][dec] = 1;
    }
    answer = -1;
    for(i=1;i<=n;i++)
        answer = max(answer,a[i][inc]+a[i][dec]);
    printf("%d\n",answer-1);    
        
}