Length of Longest Subsequence

Given an array of integers, A of length N, find the length of longest subsequence which is first increasing then decreasing.

Input Format:

The first and the only argument contains an integer array, A.

Output Format:

Return an integer representing the answer as described in the problem statement.

Constraints:

1 <= N <= 3000
1 <= A[i] <= 1e7

Example:

Input 1:
    A = [1, 2, 1]

Output 1:
    3

Explanation 1:
    [1, 2, 1] is the longest subsequence.

Input 2:
    [1, 11, 2, 10, 4, 5, 2, 1]

Output 2:
    6
    
Explanation 2:
    [1 2 10 4 2 1] is the longest subsequence.
Method:

Keep track of two dp arrays, one for increasing and one for decreasing.

Solution:

Time: O(n^2)
Space: O(n)

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int longestSubsequenceLength(final List<Integer> A) {
        int n = A.size();
        int[] inc = new int[n];
        int[] dec = new int[n];
        int max = 0;
        for (int i = 0; i < A.size(); i ++) {
            inc[i] = 1;
            for (int j = 0; j < i; j ++) {
                if (A.get(j) < A.get(i)) {
                    inc[i] = Math.max(inc[i], inc[j] + 1);
                }
            }
        }
        for (int i = A.size() - 1; i >= 0; i --) {
            dec[i] = 1;
            for (int j = A.size() - 1; j > i; j --) {
                if (A.get(j) < A.get(i)) {
                    dec[i] = Math.max(dec[i], dec[j] + 1);
                }
            }
        }
        // System.out.println(Arrays.toString(inc));
        // System.out.println(Arrays.toString(dec));
        for (int i = 0; i < A.size(); i ++) {
            max = Math.max(max, inc[i] + dec[i] - 1);
        }
        return max;
    }
}