Java (ArrayList)

Question

The following method should returns the length of the longest sorted sequence within a list of integers. For example, if a variable called list stores the following sequence of values: {11,12,30,41,5,3,7,6}, it should return 4.

When the longest sorted sequence starts at front, this method fails the test(it returns 3), but it works for the other tests. Does anybody know where the problem is? Thank you.

public int longestSortedSequence() {
 int count = 0;
 int max1 = 0;
 int max2 = 0;
 for (int i = 0; i < size; i++) {
 if (elementData[i] <= elementData[i + 1]) {
 count++;
 if (count >= max1) {
 max1 = count;
 }
 } else if (elementData[i] > elementData[i + 1]) {
 count = 0;
 count++;
 if (count >= max2) {
 max2 = count;
 }
 }
 }
 return Math.max(max1, max2);
}

• Marek Sebera: Why is this marked both Java and C# ?
• Hot Licks: How is elementData declared? What does this have to do with ArrayList?
• Hot Licks: What's the point of taking the max between max and max?
• Hot Licks: If you have 4 elements in order you will have element N compare smaller than element N+1 3 times.
• Chetter Hummin: count >= max can probably be count > max

Answer 1

Two comments:

1. For each i, you are testing whether element i+1 continues the current non-decreasing sequence. So, before the first iteration of your loop, you should already have counted element 0 as belonging to the current non-decreasing sequence; on the first iteration, you test if element 1 continues that sequence. That means count should be set to 1 in the beginning.

2. Your code will probably throw an ArrayIndexOutOfBoundsException on the last iteration of the for loop, because i+1 will equal size, which is not a valid index into your array.

Answer 2

• I guess the codes in your question were with a lot of copy-paste. e.g. the if (count>=max) parts.

• Your codes may throw IndexOutOfBoundExcep. because you read e[i+1] in your loop, and set with condition i<size

• The count should be at least 1. (descending sort case), if the array is not empty. When empty array, return 0.

I just did some fixes, and re-wrote a bit. (without writing in IDE, not tested either). Just show some idea.

public int longestSortedSequence() {
 if (size==0)return 0; //empty array
 int count = 1; //at least 1
 int max = 1;
 for (int i = 0; i < size-1; i++) {
 if (elementData[i] <= elementData[i + 1]) {
 count++; 
 } else {
 max=count>max?count:max;
 count = 1;
 }
 }
 return count>max? count: max;
}