Longest Increasing Subsequence

Work backwards from the last index

The dynamic programming array at any index i just indicates the length of the longest increasing subsequence start at index i

• Each element is a subsequence of length 1, so we initialize the array with 1

Take the example [1, 2, 4, 3]

• dp[3] = 1 because you cannot create a subsequence from the last elemtn
• Now, what's the longest increasing subsequence from index 2?\
  • It could be either dp[2], OR
  • 1 + dp[3], i.e. length of subsequence starting at index 3 plus current element at index 2
  • We take the maximum of these as per the question, so we would set
    • dp[2] = max(dp[2], 1 + dp[3])
  • Remember that this can only be done if the element at the next index is greater than the element at the current index
  • We can start multiple subsequences from the current index
    • We just need to consider the subsequence of the longest length,
      • THIS IS why we need a double for loop
• At index 1, the choice for dp[1] would be:
  • dp[1] = max(dp[1], 1 + dp[2], 1 + dp[3])
  • We need to do this because we need to consider skipping whatever characters in between,
    • Here, skipping a number is simply achieved by considering all the elements after the current element but one at a time
  • This is why the time complexity is o(n^2), because it's a double for loop

For the example nums = [10,9,2,5,3,7,101,18]

the dp array would be [2, 2, 4, 3, 3, 2, 1, 1]

• You can see how each number indicates the length of the subsequence from that particular index

FUTURE FAAEZ: DO A DRY RUN, YOU'LL UNDERSTAND