Subarray & DP

Summary

In this post, I will introduce some problems related to subarray and dynamic programming.

The most important thing in subarray is that it is continuous. So usually one dimension of the DP will be chosen as “a subarray starting at index i”. Then we need a separate loop for it to choose the best starting point.

OJ

 TrickDifficulty
LC 53 Maximum Subarray Sum3 points
LC 644Binary Search Result + Greedy + Maximum Subarray Sum6 points
LC 727 DP+Subarray+Subsequence6 points

Details

Minimum Window Subsequence

Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W.

// alg[i][j], the shortest subarray starting at i in S contains T[j:] as a subsequence.
// alg[i][n] = 0
alg[i][j] = min{
  1. 1 + alg[i + 1][j + 1] if S[i] == T[j],
  2. 1 + alg[i + 1][j],
}

Since dimension i is defined as subarray, we should add 1 even if we don’t want to use the character at i. It is wrong if we go with,

alg[i][j] = min{
  1. 1 + alg[i + 1][j + 1] if S[i] == T[j],
  2. alg[i + 1][j],
}

Leave a Reply

Your email address will not be published. Required fields are marked *