# very challenging java problem for array

This topic is 5464 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites

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.

----

##### Share on other sites
Quote:
 Original post by LawgiverIn 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.

##### Share on other sites
That's a tricky homework question for sure.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by antareusThat's a tricky homework question for sure.

##### Share on other sites
Quote:
 Original post by antareusThat's a tricky homework question for sure.
sounds more like programming team.

##### Share on other sites
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.

##### Share on other sites
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);

##### Share on other sites
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 phaelaxI understand the first sequence, but that second one he listed doesn't make sense.69,68,64,62To 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);

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 22
• 17
• 46