Longest Bitonic Subsequence

Given an array arr[0 … n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence. A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.

Examples:

Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)

Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)

Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)

class Solution {
    public int lengthOfBitonic(int[] nums) {
        if (nums.length == 0)
            return 0;
        int dpForward[] = new int[nums.length];
        int dpBackward[] = new int[nums.length];
        dpForward[0] = 1;
        dpBackward[nums.length - 1] = 1;
        for (int i = 1; i < nums.length; i++) {
            dpForward[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    dpForward[i] = Math.max(dpForward[i], dpForward[j] + 1);
            }
        }
        for (int i = nums.length - 2; i >= 0; i--) {
            dpBackward[i] = 1;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j])
                    dpBackward[i] = Math.max(dpBackward[i], dpBackward[j] + 1);
            }
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++)
            max = Math.max(max, dpForward[i] + dpBackward[i] - 1);
        return max;
    }
}