# Analyze a given array of integers and write a function to determine the length of the longest subsequent growing sequence contained within the array.


# 1,2,3,4,2,1,3
#             |

# Example 1:
# 
# Input: nums = [10,9,2,5,3,7,101,18]
#   [(2, 1), 3, 5, 7, 9, 10, 18, 101]
#    |
# Output: 4

# Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

# Example 2:
# 
# Input: nums = [0,1,0,3,2,3]
# Output: 4
# Example 3:
# 
# Input: nums = [7,7,7,7,7,7,7]
# Output: 1


# Longest Increasing Subsequence
def main(nums):
    ans = 0
    cache = set()

    def dfs(val, pos, curr_ans):
        nonlocal ans

        if ((val, pos, curr_ans) in cache):
            return

        if pos > len(nums):
            return
        if nums[pos] > val:
            curr_ans += 1
        else:
            ans = max(ans, curr_ans)
            return 
        for i in range(pos, len(nums)):
            dfs(nums[pos], i, curr_ans)

    for i in range(len(nums)):
        dfs(float("-inf"), i, 0)

    return ans


print(main([10,9,2,5,3,7,101,18]))