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; } }