Longest Bitonic Subsequence

https://www.geeksforgeeks.org/longest-bitonic-subsequence-dp-15/

package pep.Day85;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Longest_Bitonic_Subsequence {
    public static void main(String[] args) {

        int[] nums = {1, 2, 5, 3, 2};
        System.out.println(LongestBitonicSequence(nums));
    }

    public static int LongestBitonicSequence(int[] nums) {
        int n = nums.length;
        // increasing subsequence
        int[] LIS = new int[n];
        // decreasing subsequence
        int[] LDS = new int[n];

        LIS_LeftToRight(nums, LIS);
        LIS_RightToLeft(nums, LDS);

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, LIS[i] + LDS[i] - 1);
        }

        return ans;
    }

    private static void LIS_RightToLeft(int[] nums, int[] dp) {
        Arrays.fill(dp, 1);
        int n = nums.length;
        for (int endIndex = n - 1; endIndex >= 0; endIndex--) {
            for (int startIndex = endIndex + 1; startIndex < n; startIndex++) {
                if (nums[startIndex] < nums[endIndex]) {
                    dp[endIndex] = Math.max(dp[startIndex] + 1, dp[endIndex]);
                }
            }
        }
    }

    private static void LIS_LeftToRight(int[] nums, int[] dp) {
        Arrays.fill(dp, 1);
        int n = nums.length;
        for (int endIndex = 0; endIndex < n; endIndex++) {
            for (int startIndex = 0; startIndex < endIndex; startIndex++) {
                if (nums[startIndex] < nums[endIndex]) {
                    dp[endIndex] = Math.max(dp[startIndex] + 1, dp[endIndex]);
                }
            }
        }
    }

}