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
| Trick | Difficulty | |
|---|---|---|
| LC 53 | Maximum Subarray Sum | 3 points |
| LC 644 | Binary Search Result + Greedy + Maximum Subarray Sum | 6 points |
| LC 727 | DP+Subarray+Subsequence | 6 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],
}