DP問(wèn)題求解之連續(xù)子序列
continous subarrays類型問(wèn)題是求數(shù)組中連續(xù)子序列是否滿足某些條件的類型問(wèn)題秤朗。
入門級(jí)連續(xù)子序列
首先先從最簡(jiǎn)單的連續(xù)子數(shù)組問(wèn)題開始跺株，題目詳見leetcode 53 Maximum Subarray矛紫。
在給定數(shù)組（數(shù)組中的元素有正有負(fù)）中找到有最大sum和的連續(xù)子數(shù)組靶壮。用status[i]記錄以第i個(gè)元素結(jié)尾的恰画，連續(xù)子數(shù)組的sum和踪少，那么很容易寫出狀態(tài)方程：
status[i] = status[i-1] > 0?(status[i-1]+nums[i]):nums[i]
如果前一個(gè)的status[i-1]是負(fù)的批什，那只會(huì)對(duì)當(dāng)前的status[i]產(chǎn)生負(fù)的影響，所以應(yīng)直接舍棄链烈，并從當(dāng)前元素開始重新計(jì)算厉斟。
注意循環(huán)求status數(shù)組的時(shí)候使用變量記錄最大sum和，最終返回即可强衡。
參考代碼如下：
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int status[n+1];
status[0] = 0;
int maxValue = nums[0];
for(int i = 1;i<=nums.size();i++){
status[i] = max(status[i-1],0)+nums[i-1];
if(status[i] > maxValue){
maxValue = status[i];
}
}
return maxValue;
}
略升級(jí)連續(xù)子序列
和上面的題型類似捏膨，但稍微有一點(diǎn)，題目參考leetcode 152. Maximum Product Subarray食侮。
給定數(shù)組中有正有負(fù)号涯，得到乘積最大的子序列的值。計(jì)算乘積和計(jì)算和不同锯七，由于負(fù)負(fù)得正链快，所以不但要記錄以元素i結(jié)尾的最大子序列的值，也需要記錄最小子序列的值眉尸。寫出狀態(tài)轉(zhuǎn)移方程如下：
status(i,0) = max(status(i-1,0) * nums(i),max(nums(i),status(i-1,1) * nums(i)))
status(i,1) = min(status(i-1,0) * nums(i),min(nums(i),status(i-1,1) * nums(i)))
這樣就很容易寫出代碼域蜗，參考代碼如下：
int maxProduct(vector<int>& nums) {
int status[nums.size()][2];
status[0][0] = nums[0] > 0?nums[0]:0;
status[0][1] = nums[0] < 0?nums[0]:0;
int maxValue = nums[0];
for(int i = 1;i<nums.size();i++){
status[i][0] = max(status[i-1][0] * nums[i],max(status[i-1][1]*nums[i],nums[i]));
status[i][1] = min(status[i-1][0]*nums[i],min(status[i-1][1]*nums[i],nums[i]));
if(status[i][0] > maxValue){
maxValue = status[i][0];
}
}
return maxValue;
}
滿足條件的連續(xù)子序列（一）
下面介紹對(duì)要滿足某一條件的連續(xù)子序列的求解方法，如leetcode 560 Subarray Sum Equals K噪猾。嚴(yán)格的來(lái)說(shuō)這不是一道DP問(wèn)題霉祸，但是這道題的思路對(duì)后面問(wèn)題的求解有借鑒意義。
求出給定數(shù)組中連續(xù)子序列的和為K的子序列個(gè)數(shù)袱蜡。采用prefix sum的方法（prefix sum就是當(dāng)前元素及其之前元素的和）丝蹭，用一個(gè)map記錄所有元素的prefix sum和對(duì)應(yīng)個(gè)數(shù)（由于數(shù)組中元素可為負(fù)，所以會(huì)出現(xiàn)某幾個(gè)元素的prefix sum相等的情況）坪蚁。記某個(gè)元素的前綴和為sum(i)奔穿，若sum(i)-K出現(xiàn)在map中則說(shuō)明存在某個(gè)子序列其和為K。這時(shí)候只需要將map[sum(i)-k]的值加入count中即可敏晤。
參考代碼如下：
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> res;
int count = 0;
int sum = 0;
res[0] = 1;
for(int i = 0;i<nums.size();i++){
sum += nums[i];
if(res.find(sum-k) != res.end()){
count += res[sum-k];
}
res[sum]++;
}
return count;
}
滿足條件的連續(xù)子序列（二）
有了上一道題的思路基礎(chǔ)贱田，更進(jìn)一步的來(lái)看參考leetcode 523. Continuous Subarray Sum。
給定一個(gè)非負(fù)數(shù)組嘴脾，判斷數(shù)組中是否有連續(xù)子序列的和為K的整數(shù)倍男摧，且子序列的元素個(gè)數(shù)應(yīng)大于等于2。這道題的特殊情況比較多译打。
還是利用prefix sum記錄前綴和耗拓，但不同的是，對(duì)前綴和和K進(jìn)行余數(shù)處理并保存在map中扶平，如果發(fā)現(xiàn)余數(shù)在map中曾經(jīng)出現(xiàn)過(guò)則說(shuō)明帆离，其中必有子序列是K的整數(shù)倍，但這里還需要對(duì)下標(biāo)間隔進(jìn)行判斷结澄，所以map中的key為余數(shù)哥谷，value為當(dāng)前元素的下標(biāo)。
特殊情況的說(shuō)明：
- k可以為0麻献，當(dāng)k為0的時(shí)候们妥，求余運(yùn)算會(huì)出錯(cuò)
- 數(shù)組中的元素可以為0，0%任何數(shù)都為0勉吻，即整除监婶。
由于這道題個(gè)人覺得可參考的地方很多，下面給出代碼和解釋：
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> res;
int sum = 0;
//初始化這個(gè)值為-1，避免在數(shù)組中只有兩個(gè)元素時(shí)出錯(cuò)惑惶。
res[0] = -1;
for(int i = 0;i<nums.size();i++){
sum += nums[i];
if(k != 0){
sum = sum % k;
}
//這里一定要注意只有在此余數(shù)沒有出現(xiàn)過(guò)的時(shí)候更新res煮盼，避免當(dāng)數(shù)組中的元素都為0的時(shí)候一直在更新res中的值，而返回false带污。
if(res.find(sum) != res.end()){
//如果模擬過(guò)前面思路的計(jì)算過(guò)程僵控，就會(huì)發(fā)現(xiàn)真正連續(xù)子序列是從res[sum]+1開始的，所以限制條件里沒有等于鱼冀。
if(i - res[sum] > 1){
return true;
}
}
else{
res[sum] = i;
}
}
return false;
}
滿足條件的連續(xù)子序列（三）
類似的還有使連續(xù)子序列的乘積滿足某個(gè)條件的报破，如leetcode 713.Subarray Product Less Than K。
在給定的正數(shù)數(shù)組中返回所有乘積小于K的子序列的個(gè)數(shù)千绪。采用滑動(dòng)窗口充易，窗口內(nèi)的元素乘積小于K，并使用start記錄滑動(dòng)窗口的頭部下標(biāo)荸型，一旦滑動(dòng)窗口中的元素的乘積大于等于K了盹靴，則就需要將start向后移動(dòng)。
需要注意的是在移動(dòng)過(guò)程中對(duì)滿足條件的子序列的個(gè)數(shù)的記錄帆疟，實(shí)際上滑動(dòng)窗口每增加一個(gè)元素鹉究，相當(dāng)于增加了(i-start+1)個(gè)滿足條件子序列，按此規(guī)律進(jìn)行累加踪宠。
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int count = 0;
int product = 1;
int start = 0;
for(int i = 0;i<nums.size();i++){
product *= nums[i];
while(start <= i && product >= k){
product /= nums[start];
start++;
}
count += i - start + 1;
}
return count;
}
滿足條件的連續(xù)子序列（四）
和上面的那道題思路很類似自赔，也是使用滑動(dòng)窗口來(lái)解，題目詳見leetcode 209. Minimum Size Subarray Sum柳琢。
從給定正數(shù)組中绍妨，找到相加大于等于K的最短子序列。同樣的用一個(gè)滑動(dòng)窗口柬脸，且窗口內(nèi)的元素相加小于K他去，同時(shí)用start記錄滑動(dòng)窗口的頭部，當(dāng)滑動(dòng)窗口內(nèi)的元素大于等于K時(shí)倒堕，向后移動(dòng)start灾测，并更新最短子序列的值。
參考代碼如下：
int minSubArrayLen(int s, vector<int>& nums) {
int len = (int)nums.size()+1;
int sum = 0;
int start = 0;
for(int i = 0;i<(int)nums.size();i++){
sum += nums[i];
while(sum >= s){
if(i-start+1 < len){
len = i-start+1;
}
sum -= nums[start];
start++;
}
}
if(len == (int)nums.size()+1){
return 0;
}
return len;
}
多數(shù)組的連續(xù)子序列
上面介紹的都是單數(shù)組的連續(xù)子序列問(wèn)題垦巴，其實(shí)多數(shù)組問(wèn)題也很經(jīng)典媳搪，比如leetcode 718 Maximum Length of Repeated Subarray。
判斷兩個(gè)給定數(shù)組中的最長(zhǎng)連續(xù)子序列骤宣，這種題是典型的可以用空間換取時(shí)間來(lái)解決的秦爆，使用一個(gè)二維數(shù)組status(i,j)當(dāng)前位置的最長(zhǎng)子序列的長(zhǎng)度，很容易寫出狀態(tài)轉(zhuǎn)移方程：
status(i,j) = status(i-1,j-1)+1 if A[i]=B[j]
同時(shí)使用變量在循環(huán)的時(shí)候更新記錄最長(zhǎng)子序列的長(zhǎng)度最終返回即可憔披。
參考代碼如下：
int findLength(vector<int>& A, vector<int>& B) {
int len1 = (int)A.size();
int len2 = (int)B.size();
int status[len1+1][len2+1];
memset(status,0,sizeof(status));
int maxValue = 0;
for(int i = 1;i<=len1;i++){
for(int j = 1;j<=len2;j++){
if(A[i-1] == B[j-1]){
status[i][j] = status[i-1][j-1]+1;
if(status[i][j] > maxValue){
maxValue = status[i][j];
}
}
}
}
return maxValue;
}
