Jump to content
  • Advertisement
Sign in to follow this  
ryonckc2004

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
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.

In any case - "can't" help you, sorry.

Share this post


Link to post
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 this post


Link to post
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 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);

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!