very challenging java problem for array
Author
let say we have this array 68,69,54,70,68,64,70,62,67,78,98,87
data[0]=68;
data[1]=69;
data[2]=54;
data[3]=70;
data[4]=68;
data[5]=64;
data[6]=70;
data[7]=62;
data[8]=67;
data[9]=78;
data[10]=98;
data[11]=87;
how do we determine the length of the longest sequence of decreasing integers which is 70,68,64,62 and 69,68,64,62 and the number of sequences with this length(4 in this case)?
Answer is length=4 and number of sequences with length=4 is 2
Well, there is the obvious O(N²) algorithm that you can use.
Variables:
1) Current outer counter.
2) Current inner counter.
3) Max sequence (initialize at 0)
4) Numbre of sequence found (initialize at 0)
Set outer counter and inner counter to 0 in a double for loop.
In the external loop you try finding the begining of each sequence.
In the inner loop you see "how_far" you can go with the criteria that current array element is smaller than previous.
If how_far > max_seq, then max_seq = how_far and num_seq = 0
If how_far == max_seq and how_far != 0 then num_seq++
Now, translate this pseudo-code into your favorite programming language.
----
Quote:Original post by Lawgiver
In the inner loop you see "how_far" you can go with the criteria that current array element is smaller than previous.
It looks like you made the assumption that the decreasing elements need to be next to each other. But ryonckc2004's example 69,68,64,62 shows that that needn't be the case.
Use dynamic programming. In this case, let f(a, b) be the length of the longest such sequence in the range data[a] to data. You want to find f(0, n-1) by starting with f(0, 0) = 1 and building up using DP.
Quote:Original post by antareussounds more like programming team.
That's a tricky homework question for sure.
No, I would tend to suspect homework, especially because a specific language is specified for what is really an algorithms question. Most contests I've written don't care too much what language you use, but most programming courses certainly do.
In any case - "can't" help you, sorry.
In any case - "can't" help you, sorry.
I understand the first sequence, but that second one he listed doesn't make sense.
69,68,64,62
To me it looks like it skipped 54, because thats the next lowest number after 69 in the array.
So just by judging the pattern of the first sequence listed (70,60,64,62), I believe this would be a solution.
69,68,64,62
To me it looks like it skipped 54, because thats the next lowest number after 69 in the array.
So just by judging the pattern of the first sequence listed (70,60,64,62), I believe this would be a solution.
int length = 0; int tLength = 0; int sCount = 0; int tVal; for (int x=0; x<12; x++) { tLength = 1; tVal = data[x]; for (int y=x; y<11; y++) { if (data[y+1] < tVal) { tVal = data[y+1]; tLength++; System.out.println(""+tVal); } } if (tLength > length) { sCount = 1; length = tLength; } else if (tLength == length) { sCount++; } } System.out.println("Sequence length: "+length); System.out.println("Number of sequences: "+sCount);
Author
Your application does not work. the second sequence does not includes 54 because 69,54 only has the length of 2. The second sequence has a length of 4 and it is also 1 of the 2 longest sequence of decreasing integers. thats y u get 69,68,64,62
Quote:Original post by phaelax
I understand the first sequence, but that second one he listed doesn't make sense.
69,68,64,62
To me it looks like it skipped 54, because thats the next lowest number after 69 in the array.
So just by judging the pattern of the first sequence listed (70,60,64,62), I believe this would be a solution.int length = 0; int tLength = 0; int sCount = 0; int tVal; for (int x=0; x<12; x++) { tLength = 1; tVal = data[x]; for (int y=x; y<11; y++) { if (data[y+1] < tVal) { tVal = data[y+1]; tLength++; System.out.println(""+tVal); } } if (tLength > length) { sCount = 1; length = tLength; } else if (tLength == length) { sCount++; } } System.out.println("Sequence length: "+length); System.out.println("Number of sequences: "+sCount);
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
