Longest Increasing Subsequence using DP

I've been trying to solve this Dynamic Programming problem which states a following. You are given an integer N, followed by N integers. Find the longest increasing subsequence possible within the sequence given. I should also mention that the numbers don't have to be consecutive.

The program I wrote doesn't change the value of it, it just leaves everything as number 1. (you'll see what I mean in the code)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 #include<iostream>
#include<queue>

using namespace std;

const int MAXS = 1000000;


int longestSeq[MAXS];
int allNumbers[MAXS];

int main(){
int n;
cin>>n;
for (int i=0; i<n; i++){
    cin>>allNumbers[i];
}
for (int i=n-1; i>=0; i--){
    longestSeq[i] = 1;
    for (int j=0; j<i; j++){
/*Here it is supposed to change the value of longestSeq[i], but it doesn't */
        if (allNumbers[i]>allNumbers[j]){
            longestSeq[i] = max(longestSeq[i], 1+longestSeq[j]);
        }
    }
}
sort(longestSeq, longestSeq+n);
cout<<longestSeq[n-1];
}
I really suggest you'll try to solve it yourself, but if you're really stuck you can read this article about the dp solution.
http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/
Last edited on
I've been trying to solve this myself, and actually I have solved it now. Thanks anyway.
Topic archived. No new replies allowed.