Leet Code 300. Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/ 

package pep.Day84;

import java.sql.Array;
import java.util.Arrays;

public class LeetCode_300_Longest_Increasing_Subsequence {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS_recursion(nums));
        System.out.println(lengthOfLIS_memoisation(nums));

        System.out.println(lengthOfLIS_tabulation(nums));
    }

    static int finalAnswer = 1;

    public static int lengthOfLIS_recursion(int[] nums) {
        finalAnswer = 1;
        int n = nums.length;
        LIS_recursion(nums, n - 1);

        return finalAnswer;
    }

    public static int LIS_recursion(int[] nums, int endIndex) {

        int maxLength = 1;
        for (int startingIndex = 0; startingIndex < endIndex; startingIndex++) {
            // har element ne apna apna LIS laa kr diya
            int len = LIS_recursion(nums, startingIndex);

            // jiska LIS chotta hoga, uske lea check krenge
            if (nums[startingIndex] < nums[endIndex]) {
                int l = len + 1;

                // jo bhi length aae usko maxLength se compare krenge
                maxLength = Math.max(maxLength, l);
            }
        }
        finalAnswer = Math.max(finalAnswer, maxLength);
        return maxLength;
    }


    public static int lengthOfLIS_memoisation(int[] nums) {
        finalAnswer = 1;
        int n = nums.length;
        LIS_memoisation(nums, n - 1, new int[n]);

        return finalAnswer;
    }

    public static int LIS_memoisation(int[] nums, int endIndex, int[] dp) {
        if (dp[endIndex] != 0)
            return dp[endIndex];
        int maxLength = 1;
        for (int startingIndex = 0; startingIndex < endIndex; startingIndex++) {
            // har element ne apna apna LIS laa kr diya
            int len = LIS_memoisation(nums, startingIndex, dp);

            // jiska LIS chotta hoga, uske lea check krenge
            if (nums[startingIndex] < nums[endIndex]) {
                int l = len + 1;

                // jo bhi length aae usko maxLength se compare krenge
                maxLength = Math.max(maxLength, l);
            }
        }
        finalAnswer = Math.max(finalAnswer, maxLength);
        return dp[endIndex] = maxLength;
    }

    public static int lengthOfLIS_tabulation(int[] nums) {
//        finalAnswer = 1;
        int n = nums.length;
        int[] dp = new int[n];
//        LIS_recursion(nums, n - 1);
        return LIS_tabulation(nums, dp);
//
//        return finalAnswer;
    }

    private static int LIS_tabulation(int[] nums, int[] dp) {

        // by default 1 toh hoga hi sabme
        Arrays.fill(dp, 1);


        int maxLength = 1;
        for (int endIndex = 0; endIndex < nums.length; endIndex++) {
            for (int startingIndex = 0; startingIndex < endIndex; startingIndex++) {
                // jiska LIS chotta hoga, uske lea check krenge
                if (nums[startingIndex] < nums[endIndex]) {
                    dp[endIndex] = Math.max(dp[endIndex], dp[startingIndex] + 1);
                }
            }

            maxLength = Math.max(maxLength, dp[endIndex]);

        }
        return maxLength;
    }
}