C++

Forum

 
longest subsequence

cetare (3)
Hello, my program should output the longest increasing subsequence.
But when i run it it it stops exactly after i give the input.
This is in russian and for me it's hard to translate it in english exactly, so i show the image.

http://i.imgur.com/TZmqJXy.png
Why does it show this and how to solve it?
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
 

#include <iostream>
#include <array>
using namespace std;
int clmsubsir(int v[],int n, int subsir[])
{
    int lungime,inceput;
    int *maxime =new int[n];
    int *urmatoru =new int[n];
    maxime[n-1]=1;
    urmatoru[n-1]=-1;
    for (int i=n-2; n>=0;n--){
        maxime[i]=1;
        urmatoru[i]=-1;
        for (int j=i+1;j<n;j++)
            if (v[i]<=v[j] && maxime[i]<=maxime[j])
            {
                maxime[i]=maxime[j]+1;
                urmatoru[i]=j;
            }}
            lungime=maxime[0];
            inceput=0;
            for (int i=1;i<n;i++)
            {
                if (lungime<maxime[i])
                {
                    lungime=maxime[i];
                    inceput=i;
                }
            }
            subsir[0]=v[inceput];
            for(int g=1;g<lungime;g++)
            {
                inceput=urmatoru[inceput];
                subsir[g]=v[inceput];

            }
            delete maxime;
            delete urmatoru;
            return lungime;

    }

int main()
{
    int n,t;
    cin>>n;

    int sir[n],subsir[n];
    for (int i=0;i<n;i++)
    {
        cin>>sir[i];

        }
t=clmsubsir(sir,n,subsir);

for (int i=0;i<t;i++)
    {
        cout<<subsir[i]<<' ';
        }

return 0;
}
Last edited on
MikeyBoy (5631)
Line 50 is not legal C++:

int sir[n],subsir[n];

The array size has to be a constant that's known at compile-time.

Have you tried stepping through your code in a debugger, to find out where it's crashing?
cetare (3)
No i haven't "forgot : )", only after your reply i tried.
Yes, you are right, it crashes at line 50.
But why isn't the constant known?
Since from line 48 the compiler already knows n.
Last edited on
shadowmouse (539)
When the program is compiled (before it is run), the compiler does not know the value of n, hence it does not know how much space to allocate for sir and subsir.
cetare (3)
Thx
Topic archived. No new replies allowed.