Leet Code 673. Number of Longest Increasing Subsequence

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

package pep.Day85;

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

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

        int[] nums = {1, 3, 5, 4, 7};
        System.out.println(findNumberOfLIS(nums));
    }

    public static int findNumberOfLIS(int[] nums) {
        int maxLength = 1, maxCount = 1;

        int n = nums.length;
        int[] dp = new int[n];
        int[] count = new int[n];

        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);

        for (int endIndex = 1; endIndex < n; endIndex++) {
            for (int startIndex = 0; startIndex < endIndex; startIndex++) {
                if (nums[startIndex] < nums[endIndex]) {
                    // aab mujhe sabse bade wala cheye

                    if (dp[startIndex] + 1 > dp[endIndex]) {
                        dp[endIndex] = dp[startIndex] + 1;
                        count[endIndex] = count[startIndex];
                    } else if (dp[startIndex] + 1 == dp[endIndex]) {
                        // iss baar dono ki values same ho gae, toh sirf count me new wala add kr do
                        count[endIndex] += count[startIndex];
                    }
                }
            }
            if (dp[endIndex] > maxLength) {
                maxLength = dp[endIndex];
                maxCount = count[endIndex];
            } else if (dp[endIndex] == maxLength) {
                maxCount = count[endIndex];
            }

        }

        return maxCount;
    }
}