10 - Longest Increasing Subsequence - Dynamic Programming approach

@Rishi Srivastava Using Dynamic programming bottom up approach, we start with computing Longest Increasing Subsequence (LIS) for whole input array. Optimal Substructure: Let nums[] be the input array and LIS(i) be the length of the LIS ending at index i such that nums[i] is the last element of the LIS. Then, LIS(i) can be recursively written as: - Starting from last n-1 index, we iterate and compute LIS for each - LIS(i) = MAX(1, 1 max( LIS(j) ) where j = i and nums[i] is less than nums[j]; or - LIS(i) = 1, if no such j exists. To find the LIS for a given array, we need to return max(LIS(i)) Github: Leetcode: