gistfile1.txt

package me.fixpoint.sandbox.java;

import static java.lang.Math.max;

class Solution {
	public static void main(String[] args) {
		System.out.println(new Solution().sequence(new int[] { 9, 10, 2, -1, 3, -5, 0, -3, 1, 12, 5, 8, -2, 6, 4 }));
	}

	private static final int NONE = -1;

	public int sequence(int[] A) {
		int[] left = new int[A.length];
		int[] right = new int[A.length];
		int[] stack = new int[A.length];
		int stackLen = 0;

		for (int index = 0; index < A.length; ++index) {
			int value = A[index];

			while (stackLen > 0 && value > A[stack[stackLen - 1]]) {
				right[stack[stackLen - 1]] = index;
				--stackLen;
			}

			if (stackLen == 0) {
				left[index] = NONE;
			} else {
				left[index] = stack[stackLen - 1];
			}

			stack[stackLen++] = index;
			right[index] = NONE;
		}

		int[] length = new int[A.length];
		int maxLength = 0;

		for (int index = 0; index < A.length; ++index) {
			maxLength = max(maxLength, computeLength(index, length, left, right));

		}

		return maxLength;
	}

	public int computeLength(int start, int[] length, int[] left, int[] right) {
		if (start == NONE) {
			return 0;
		}

		if (length[start] == 0) {
			int leftLen = computeLength(left[start], length, left, right);
			int rightLen = computeLength(right[start], length, left, right);
			length[start] = 1 + max(leftLen, rightLen);
		}

		return length[start];
	}
}