DP problem

[nitin1]

#include<stdio.h>

int dp[20];

int lis(int a[],int n)
{
    int i,j,sum=0;
    dp[0]=1;
    for(i=0;i<6;i++)
    {
         for(j=i+1;j<n;j++)
         {
              if(a[j]>=a[i])
              {
                    dp[j]=dp[j-1]+1;        
              }
              else
              dp[j]=dp[j-1];
         }
    }
}


int main()
{
    int a[]={ 5, 3, 4, 8, 6, 7};
    int i=0;

    lis(a,6);

    for(i=0;i<6;i++)
    printf("%d ",dp[i]);
    getch();
    return 0;
}

hi , this is the code to print Longest increasing sequence in the given n numbers. but i want a little bit change in this that i want to tell the number of increasing sequqnces of length k , say 3 in this case. then what and where should i add something so as to do this. thanks

[nmaillet]

That seems way more complex then it needs to be. You should be able to do that with one for-loop and without the dp array. You can use a few of variables, such as count, max_count and max_num. Use count for each sequence. Once your done with a sequence (i.e. number less than the last), if count equals max_count, increment max_num. Otherwise, if count is greater than max_count, set max_count to count and reset max_num to 1. Simplify your code, and give it a try.

[nitin1]

are you trying to simplify my this code or are you giving answer of my question ? I didnt get it sorry to say this!

[np complete]

Actually your code runs in n^2. nmaillet is asking you to optimize your code so hat it runs in O( n log n).

[nitin1]

this is a second issue! firstly tell me that how to find the number of increasing sequences of length k in n numbers, i mean how to modify this code a little so as to achieve the goal. later , i will think to optimize it. thanks