# Solving Leetcode Interviews in Seconds with AI: Number of Longest Increasing Subsequence


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "673" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# Problem Statement
	> Given an integer array nums, return the number of longest increasing subsequences. Notice that the sequence has to be strictly increasing.   Example 1:  Input: nums = [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].  Example 2:  Input: nums = [2,2,2,2,2] Output: 5 Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.    Constraints:  1 <= nums.length <= 2000 -106 <= nums[i] <= 106 The answer is guaranteed to fit inside a 32-bit integer.  

	# Explanation
	Here's a breakdown of the approach and the Python code:

*   **Dynamic Programming:** Use two arrays, `length` and `count`, to store the length of the longest increasing subsequence ending at each index and the number of such subsequences, respectively.
*   **Iterative Calculation:** Iterate through the `nums` array. For each element, iterate through the elements before it. If a smaller element is found, update the `length` and `count` arrays based on the lengths and counts of the subsequences ending at the smaller element.
*   **Result Aggregation:** Find the maximum length of all increasing subsequences and sum the counts of subsequences that achieve this maximum length.

*   **Runtime Complexity:** O(n^2), where n is the length of the input array. **Storage Complexity:** O(n).

	
	# Code
	```python
	def findNumberOfLIS(nums):
    n = len(nums)
    if n == 0:
        return 0

    length = [1] * n
    count = [1] * n

    for i in range(n):
        for j in range(i):
            if nums[i] > nums[j]:
                if length[j] + 1 > length[i]:
                    length[i] = length[j] + 1
                    count[i] = count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]

    max_len = max(length)
    ans = 0
    for i in range(n):
        if length[i] == max_len:
            ans += count[i]

    return ans
	```