Number of Longest Increasing Subsequence

class Solution {
public:
    int computeLISCount(std::vector<int>& sequence) {
        int sz = sequence.size();
        vector<int> dp(sz, 0);
        vector<int> cnt(sz, 0);
    
        function<void(int)> processLIS = [&](int idx) {
            if (dp[idx] != 0)
                return;
    
            dp[idx] = 1;
            cnt[idx] = 1;
            for (int k = 0; k < idx; k++) {
                if (sequence[k] < sequence[idx]) {
                    processLIS(k);
                    if (dp[k] + 1 > dp[idx]) {
                        dp[idx] = dp[k] + 1;
                        cnt[idx] = 0;
                    }
                    if (dp[k] + 1 == dp[idx]) {
                        cnt[idx] += cnt[k];
                    }
                }
            }
        };
    
        int maxLISLength = 0;
        int totalNumbers = 0;
        for (int i = 0; i < sz; i++) {
            processLIS(i);
            if (dp[i] > maxLISLength)
                maxLISLength = dp[i];
        }
    
        for (int i = 0; i < sz; i++) {
            if (dp[i] == maxLISLength)
                totalNumbers += cnt[i];
        }
    
        return totalNumbers;
    }
};

The given C++ solution finds the number of longest increasing subsequences in an array. Below is a high-level explanation of how the function computeLISCount is implemented:

• The function accepts a vector of integers, named sequence, which represents the array.
• Two vectors, dp and cnt, are used. dp[i] stores the length of the longest increasing subsequence ending at index i, and cnt[i] stores the count of such subsequences.
• A recursive lambda function, processLIS, is employed to calculate the values in dp and cnt. This function leverages dynamic programming to build results based on previously computed values.
• For each index i:
  • Initialization sets dp[i] = 1 and cnt[i] = 1, as every single element is trivially a subsequence of length 1.
  • The function then checks all previous indices k to see if extending a subsequence ending at k with sequence[i] forms a longer or another longest subsequence at i.
  • Depending on the comparison of subsequences lengths, the function updates dp and cnt accordingly.
• After determining the dp and cnt values for each index, two additional integer variables, maxLISLength and totalNumbers, help identify the overall longest subsequences and their counts:
  • maxLISLength keeps track of the maximum length identified.
  • totalNumbers sums up counts of subsequences that have the longest length.
• The primary loop iterates through each element in the array, triggering the lambda function to process each index.
• Each subsequence's length and count are compared to maxLISLength and summed up in totalNumbers if they match the maximum length.
• Finally, totalNumbers, representing the total count of maximum length subsequences, is returned.

To use this solution, instantiate the Solution class and call the computeLISCount method with the input array. Ensure the vector and function utilities from the C++ Standard Library are included in your environment to handle data structures and lambda functions effectively.

class Solution {
    public int countLIS(int[] arr) {
        int size = arr.length;
        int[] dpLength = new int[size];
        int[] dpCount = new int[size];
        int maxLen = 0;
        int totalLIS = 0;
        for (int k = 0; k < size; k++) {
            processDP(k, arr, dpLength, dpCount);
            maxLen = Math.max(maxLen, dpLength[k]);
        }
    
        for (int k = 0; k < size; k++) {
            if (dpLength[k] == maxLen) {
                totalLIS += dpCount[k];
            }
        }
    
        return totalLIS;
    }
    
    private void processDP(int idx, int[] arr, int[] dpLength, int[] dpCount) {
        if (dpLength[idx] != 0) {
            return;
        }
    
        dpLength[idx] = 1;
        dpCount[idx] = 1;
    
        for (int prev = 0; prev < idx; prev++) {
            if (arr[prev] < arr[idx]) {
                processDP(prev, arr, dpLength, dpCount);
                if (dpLength[prev] + 1 > dpLength[idx]) {
                    dpLength[idx] = dpLength[prev] + 1;
                    dpCount[idx] = 0;
                }
                if (dpLength[prev] + 1 == dpLength[idx]) {
                    dpCount[idx] += dpCount[prev];
                }
            }
        }
    }
}

This Java solution tackles the problem of finding the number of longest increasing subsequences within an array. The method countLIS implements dynamic programming to calculate the length of the longest subsequence at each position in the array using two key arrays: dpLength and dpCount.

• dpLength: Stores the lengths of the longest subsequences ending at each index.
• dpCount: Tracks the counts of these longest subsequences at each index.

Initially, each position's longest increasing subsequence is at least itself, so dpLength is initialized to 1 for all indices, and correspondingly, dpCount is also initialized to 1 since each element is a subsequence.

The method processDP is used within countLIS to update dpLength and dpCount:

• It's a recursive function that ensures each element's longest increasing subsequence is determined in relation to every other previous element.
• If an element at a previous index is less than the current element, processDP is called for that previous index.
• After returning from the recursion, lengths and count updates occur based on conditions if the subsequence including the current element exceeds the already known subsequences.

The countLIS function also maintains a variable maxLen to keep track of the maximum length of subsequences found. Then, to gather the result, it sums up counts from dpCount where the lengths equal maxLen.

Finally, this approach returns totalLIS, the total number of longest increasing subsequences found in the entire array. This solution efficiently combines recursive computation and dynamic programming paradigms to solve the problem.

class Solution:
    def calculateLISCount(self, sequence):
        size = len(sequence)
        lis_length = [0] * size
        ways_to_form_lis = [0] * size
    
        def process_dynamics(index):
            if lis_length[index] != 0:
                return
    
            lis_length[index] = 1
            ways_to_form_lis[index] = 1
    
            for preceding in range(index):
                if sequence[preceding] < sequence[index]:
                    process_dynamics(preceding)
                    if lis_length[preceding] + 1 > lis_length[index]:
                        lis_length[index] = lis_length[preceding] + 1
                        ways_to_form_lis[index] = 0
                    elif lis_length[preceding] + 1 == lis_length[index]:
                        ways_to_form_lis[index] += ways_to_form_lis[preceding]
    
        longest_seq_length = 0
        total_ways = 0
        for current in range(size):
            process_dynamics(current)
            longest_seq_length = max(longest_seq_length, lis_length[current])
    
        for current in range(size):
            if lis_length[current] == longest_seq_length:
                total_ways += ways_to_form_lis[current]
    
        return total_ways

The provided solution in Python addresses the problem of finding the number of longest increasing subsequences within a given sequence. The solution utilizes dynamic programming to solve this problem efficiently. Below is the breakdown of the solution process:

• Initialize two lists, lis_length and ways_to_form_lis.

  • lis_length keeps track of the longest increasing subsequence length at each index.
  • ways_to_form_lis stores how many ways the LIS length can be obtained for each index.

• Define a helper function process_dynamics that uses recursion and memoization to avoid recalculating the LIS information for already processed indices.

  • For each element, check if it can extend the subsequences ending with any preceding elements less than itself.
  • Update the lis_length and ways_to_form_lis accordingly, ensuring to distinguish between extending an existing LIS (increasing count) or finding a longer one (reset count).

• Iterate over the sequence to process each element using process_dynamics, concurrently updating the maximum length of the LIS found so far (longest_seq_length).

• After determining the longest sequence possible, iterate once more over the array to sum up the ways each index contributes to that maximum length, resulting in total_ways.

• Finally, return total_ways, which represents the total number of distinct longest increasing subsequences found in the input sequence.

This approach effectively combines dynamic programming with depth-first traversal to compute both the length and count of the longest increasing subsequences in a single pass, possibly with additional recursive depth due to the process_dynamics function.