Java implementation of the longest monotone increasing subsequence

Question

Problem: Given a set of n distinct numbers, find the length of the longest monotone increasing subsequence. For example, let's take this array [1,2,9,4,7,3,11,8,14,6] The longest monotone increasing subsequence of this array is [1,2,4,7,11,14]. So the desired result is, the length of the array which is 6.

Algorithm (taken from R.G. Dromey's How to Solve it by computer):

1. Establish the data set a[1...n] of n elements.
2. Set two loops, one to find out out each terminating point and the inner loop to find it's increasing subsequence.
3. start the first loop at index 2 so that it will initially have a sequence.
4. in the inner loop, if current element is less than maximum of previous sequence, then, identify the subsequence and if the length of subsequence is larger than the length of previous longest subsequence then update the length, position of maximum and maximum value.

else, update the length, position of maximum and maximum value so far.

import java.util.*;

public class Monotone {

  public static int maxMonotonicSequenceLength(int[] elements) {
    int maxValue = 0;
    int positionOfMax = 0;
    int length = 2;

    for (int i = 2; i < elements.length; ++i) {
      if (elements[i] < maxValue) {
        int count = 1;
        int previousMaxElement = 0;

        for (int j = 1; j <= i-1; ++j) {
          if ((elements[j] < elements[i]) &&
              previousMaxElement < elements[j]) {

            previousMaxElement = elements[j];
            count = count + 1;
            if (length < count) {
              length = count;
              positionOfMax = j;
              maxValue = elements[j];
            }
          }
        }
      } else {
        positionOfMax = i;
        maxValue = elements[i];
        length = length + 1;
      }
    }
    return length + 1;
  }

  public static void main(String args[]) {
    int[] list = new int[10];

    list[0] = 1;
    list[1] = 2;
    list[2] = 9;
    list[3] = 4;
    list[4] = 7;
    list[5] = 3;
    list[6] = 11;
    list[7] = 8;
    list[8] = 14;
    list[9] = 6;

    System.out.println("lenght of subsequence: " + maxMonotonicSequenceLength(list));
  }
}

Answer 1

Coding details

• You can initialize list like this : int[] list = {1,2,9,4,7,3,11,8,14,6};
• for (int j = 1, n = i-1; j <= n; ++j) { // do not loop on limit calculation
• length++; // for length = length + 1;