1.最大子數(shù)組

題目鏈接：53. 最大子數(shù)組和 - 力扣（LeetCode）

題目描述：找出nums數(shù)組中的最大和連續(xù)數(shù)組，并返回其最大和

算法講解：動(dòng)態(tài)規(guī)劃

1.狀態(tài)表示：經(jīng)驗(yàn)+題目要求

經(jīng)驗(yàn)：以某位置為結(jié)尾，什么什么什么

在這道題中，因?yàn)橐页鲎畲蠛偷倪B續(xù)子數(shù)組，并返回這個(gè)最大和，所以在這道題中，可以將dp[i]表示為：以i位置為結(jié)尾的所有子數(shù)組中的最大和

2.狀態(tài)轉(zhuǎn)移方程：

做這種線性dp的問題，要畫圖來分析，由于要找出以i位置為結(jié)尾的所有子數(shù)組的最大和，首先就要找出nums數(shù)組所有以i為結(jié)尾的子數(shù)組，此時(shí)找出的子數(shù)組可以劃分為兩種情況，一種是長(zhǎng)度為1的子數(shù)組，另一種情況是長(zhǎng)度大于1的子數(shù)組。

第一種情況：長(zhǎng)度為1的子數(shù)組

長(zhǎng)度為1的子數(shù)組就是nums[i]，此時(shí)的子數(shù)組的最大和就是nums[i]，所以此時(shí)dp[i]=nums[i]

第二種情況：長(zhǎng)度大于1的子數(shù)組

當(dāng)子數(shù)組的長(zhǎng)度大于1時(shí)，此時(shí)子數(shù)組可以看成由一個(gè)以單獨(dú)nums[i]組成的數(shù)組和一個(gè)以i-1的位置為結(jié)尾的數(shù)組組成的數(shù)組，如下圖

此時(shí)要想求dp[i]，此時(shí)就要知道以i-1位置為結(jié)尾的子數(shù)組的最大和，根據(jù)狀態(tài)表示，可以用dp[i-1]表示以i-1位置為結(jié)尾的子數(shù)組的最大和，此時(shí)dp[i]=dp[i-1]+nums[i]

因?yàn)橐蟮氖亲畲蠛?#xff0c;所以最終的狀態(tài)轉(zhuǎn)移方程為：

dp[i]=Math.max(nums[i]，dp[i-1]+nums[i])?

3.初始化?

此時(shí)由于求dp[i]時(shí)會(huì)用到dp[i-1]，所以要初始化dp[0]，dp[0]表示以第1個(gè)位置為結(jié)尾的所有子數(shù)組的最大和，因?yàn)?是數(shù)組的起始位置，此時(shí)就要將dp[0]=nums[0]

4.填表順序

從左往右填dp表即可

5.返回值

要返回dp表中的最大值

代碼實(shí)現(xiàn)：

//暴力枚舉
class Solution {public int maxSubArray(int[] nums) {int n=nums.length;int ret=Integer.MIN_VALUE;int sum=0;for(int i=0;i<n;i++){for(int j=i;j<n;j++){if(i==j) sum=0;sum+=nums[j];ret=Math.max(ret,sum);}}return ret;}
}//動(dòng)態(tài)規(guī)劃
class Solution {public int maxSubArray(int[] nums) {int n=nums.length;int[] dp=new int[n];dp[0]=nums[0];for(int i=1;i<n;i++)dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);int ret=dp[0];for(int i=0;i<n;i++)if(ret<dp[i]) ret=dp[i];return ret;}
}

2.環(huán)形數(shù)組的最大和?

題目鏈接：918. 環(huán)形子數(shù)組的最大和 - 力扣（LeetCode）?

?題目解析：不用看圖片中的題目，看也看不懂，只需要知道nums是一個(gè)環(huán)形數(shù)組就行了

算法講解：

1.狀態(tài)表示：

首先分析一下題目，由于nums數(shù)組是一個(gè)環(huán)形數(shù)組，所以在環(huán)形數(shù)組中選擇的子數(shù)組會(huì)有兩種情況，如下圖

第一種情況就是子數(shù)組是在nums中的藍(lán)色部分，此時(shí)直接求出藍(lán)色部分的子數(shù)組中最大和即可

第二種情況就是選中的子數(shù)組，一部分是在尾部，一部分在頭部，因?yàn)槭黔h(huán)形數(shù)組，所以這兩部分也是連續(xù)的，但是此時(shí)直接求出最大和是有點(diǎn)困難的，但是可以裝換一下思路， 因?yàn)閚ums數(shù)組的總和是固定的，此時(shí)要求最大和，只要求出中間那部分子數(shù)組中的最小和，通過總和減去中間部分的最小和，可以間接得到最大和，如下圖

所以，此時(shí)就會(huì)有兩種狀態(tài)表示：

f[i]表示：以i位置為結(jié)尾的所有子數(shù)組中的最大和

g[i]表示：以i位置為結(jié)尾的所有子數(shù)組中的最小和?

2.狀態(tài)轉(zhuǎn)移方程

因?yàn)橛袃蓚€(gè)狀態(tài)表示，所以狀態(tài)轉(zhuǎn)移方程也有兩種

推算f[i]，推算f[i]時(shí)，子數(shù)組也可以分為兩種，分別是長(zhǎng)度為1的子數(shù)組和長(zhǎng)度不為1的子數(shù)組，如下圖

當(dāng)子數(shù)組的長(zhǎng)度為1時(shí)，此時(shí)子數(shù)組就是nums[i]，所以此時(shí)f[i]=nums[i]

當(dāng)子數(shù)組的長(zhǎng)度大于1時(shí)，此時(shí)要計(jì)算f[i]，就要知道以i-1位置為結(jié)尾的所有子數(shù)組中的最大和，根據(jù)f[i]的狀態(tài)表示，f[i-1]可以表示以i-1位置為結(jié)尾的所有子數(shù)組中的最大和，此時(shí)f[i]=f[i-1]+nums[i]?

因?yàn)橐蟮氖亲畲蠛?#xff0c;所以f[i]的狀態(tài)轉(zhuǎn)移方程為：

f[i]=Math.max(nums[i]，nums[i]+f[i-1])

推理g[i]的狀態(tài)轉(zhuǎn)移方程的過程一模一樣，同理可得：

g[i]=Math.min(nums[i]，nums[i]+g[i-1])?

3.初始化

此時(shí)為了方便初始化，可以多創(chuàng)建一部分空間來實(shí)現(xiàn)初始化，初始化時(shí)有兩個(gè)注意事項(xiàng)：

第一個(gè)注意事項(xiàng)：虛擬空間填的值要保證后面的填表正確

假設(shè)沒有多創(chuàng)建空間，原本f[0]和g[0]要填的值就是nums[0]，如果多創(chuàng)建了空間后，原本的f[0]和g[0]就變成了f[1]和g[1]，此時(shí)的f[0]和g[0]就是多創(chuàng)建的空間，此時(shí)要想nums[0]被選上，只要將f[0]和g[0]初始化為0即可，因?yàn)閚ums[0]+0的結(jié)果還是nums[0]

4.填表順序

由于填表時(shí)用到了i-1，所以要從左往右填表

5.返回值

此時(shí)是有一個(gè)細(xì)節(jié)的，如果nums數(shù)組中全是負(fù)數(shù)，此時(shí)直接返回fmax即可，如果數(shù)組中不全是負(fù)數(shù)，返回Math.max(fmax，sum-gmin)即可

代碼實(shí)現(xiàn)：

//我寫的版本
class Solution {public int maxSubarraySumCircular(int[] nums) {int n=nums.length;if(n==1) return nums[0];int sum=0;for(int i=0;i<n;i++) sum+=nums[i];int[] f=new int[n+1];int[] g=new int[n+1];f[0]=g[0]=0;for(int i=1;i<n+1;i++){f[i]=Math.max(nums[i-1],f[i-1]+nums[i-1]);g[i]=Math.min(nums[i-1],g[i-1]+nums[i-1]);}int max=Integer.MIN_VALUE;int min=Integer.MAX_VALUE;for(int i=1;i<n+1;i++){if(max<f[i]) max=f[i];if(min>g[i]) min=g[i];}return sum==min?max:Math.max(max,sum-min);}
}//另一個(gè)版本
class Solution {public int maxSubarraySumCircular(int[] nums) {int n=nums.length;int[] f=new int[n+1];int[] g=new int[n+1];int max=Integer.MIN_VALUE;int min=Integer.MAX_VALUE;int sum=0;for(int i=1;i<n+1;i++){int x=nums[i-1];f[i]=Math.max(nums[i-1],nums[i-1]+f[i-1]);max=Math.max(max,f[i]);g[i]=Math.min(nums[i-1],nums[i-1]+g[i-1]);min=Math.min(min,g[i]);sum+=x;}return sum==min ? max : Math.max(max,sum-min);}
}

3.乘積最大子數(shù)組?

題目鏈接：152. 乘積最大子數(shù)組 - 力扣（LeetCode）?

題目描述：在nums數(shù)組中找出一個(gè)非空連續(xù)子數(shù)組，且該子數(shù)組的乘積最大，并返回該子數(shù)組的乘積

算法講解：動(dòng)態(tài)規(guī)劃

1.狀態(tài)表示

其實(shí)這道題和第二道題很相似，一開始肯定只會(huì)想到用一個(gè)dp[i]來表示以i位置為結(jié)尾的所有子數(shù)組的最大和，但是這道題求的是乘積，且nums數(shù)組中的nums[i]可能出現(xiàn)負(fù)數(shù)的情況，當(dāng)f[i]是一個(gè)很大的數(shù)時(shí)，如果接著遇到nums[i]是一個(gè)負(fù)數(shù)，那么之后f[i]就會(huì)變成一個(gè)很小的數(shù)，所以此時(shí)還要記錄以i位置為結(jié)尾的的所有子數(shù)組中的最小和，所以最終的狀態(tài)表示有2個(gè)：

f[i]表示：以i位置為結(jié)尾的所有子數(shù)組中的最大乘積

g[i]表示：以i位置為結(jié)尾的所有子數(shù)組總的最小乘積

2.狀態(tài)表示

因?yàn)闋顟B(tài)表示有兩個(gè)，所以推算狀態(tài)方程時(shí)也有兩種

1.推算f[i]的狀態(tài)轉(zhuǎn)移方程

在推算f[i]時(shí)，子數(shù)組也可以分為2種情況，可以分為長(zhǎng)度為1的子數(shù)組和長(zhǎng)度大于1的子數(shù)組，如下圖

當(dāng)子數(shù)組的長(zhǎng)度為1時(shí)，此時(shí)nums[i]就是子數(shù)組，此時(shí)f[i]=nums[i]?

當(dāng)子數(shù)組的長(zhǎng)度不為1時(shí)，如果按照我們平時(shí)的慣性思維，此時(shí)要求f[i]，就要先求出f[i-1]，也就是要求出以i-1位置為結(jié)尾時(shí)的所有子數(shù)組中的最大乘積，此時(shí)就得出f[i]=f[i-1]*nums[i]，但是這一道題的nums[i]有可能是負(fù)數(shù)的情況，一個(gè)小的數(shù)與一個(gè)負(fù)數(shù)相乘就會(huì)變成一個(gè)大的數(shù)，而g[i]就表示以i位置為結(jié)尾的所有子數(shù)組中的最小乘積，所以此時(shí)f[i]=g[i-1]*nums[i]

如下圖：

但是要求的是最大乘積，所以最終f[i]的狀態(tài)轉(zhuǎn)移方程為：

f[i]=max(nums[i],f[i-1]*nums[i],g[i-1]*nums[i])?

同理可得，g[i]的狀態(tài)轉(zhuǎn)移方程：

g[i]=min(nums[i],g[i-1]*nums[i-1],f[i-1]*nums[i-1])?

3.初始化

在這里，依舊選擇創(chuàng)建虛擬節(jié)點(diǎn)來實(shí)現(xiàn)初始化，有兩個(gè)注意事項(xiàng)：

第一個(gè)注意事項(xiàng)：虛擬節(jié)點(diǎn)填的值要保證后面的天表正確

填加了虛擬節(jié)點(diǎn)后，此時(shí)的f[1]就是原來的f[0]，此時(shí)初始化f[1]時(shí)，是要將f[1]初始化為nums[0]的，但是初始化時(shí)用到了f[i]=max(nums[i],f[i-1]*nums[i],g[i-1]*nums[i]) ，此時(shí)要保證max時(shí)讓nums[i]被選到，此時(shí)直接將f[0]和g[0]初始化為1就行了，因?yàn)閚ums[i]*1的結(jié)果也是nums[i]

第二個(gè)注意事項(xiàng)：注意下標(biāo)的映射關(guān)系

4.填表順序

要從左往右同時(shí)填f表和g表

5.代碼實(shí)現(xiàn)

class Solution {public int maxProduct(int[] nums) {int n=nums.length;if(n==1) return nums[0];int[] f=new int[n+1];int[] g=new int[n+1];f[0]=1;g[0]=1;int ret=Integer.MIN_VALUE;for(int i=1;i<n+1;i++){f[i]=Math.max(nums[i-1],Math.max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));g[i]=Math.min(nums[i-1],Math.min(g[i-1]*nums[i-1],f[i-1]*nums[i-1]));if(f[i]>ret) ret=f[i];}return ret;}
}

4.乘積為正數(shù)的最長(zhǎng)子數(shù)組的長(zhǎng)度?

題目鏈接：1567. 乘積為正數(shù)的最長(zhǎng)子數(shù)組長(zhǎng)度 - 力扣（LeetCode）?

題目描述：返回nums數(shù)組中乘積為正數(shù)的最長(zhǎng)子數(shù)組的長(zhǎng)度

算法講解：動(dòng)態(tài)規(guī)劃

1.狀態(tài)表示：經(jīng)驗(yàn)+題目要求

根據(jù)題目要求，首先會(huì)設(shè)計(jì)出一個(gè)狀態(tài)表示，用f[i]來表示：

f[i]表示：以i位置為結(jié)尾的所有子數(shù)組中乘積為正數(shù)的最長(zhǎng)長(zhǎng)度

g[i]表示：以i位置為結(jié)尾的所有子數(shù)組中乘積為負(fù)數(shù)的最長(zhǎng)長(zhǎng)度

2.狀態(tài)轉(zhuǎn)移方程：

因?yàn)槭亲訑?shù)組問題，子數(shù)組的情況任然可以分為2中情況，分別是長(zhǎng)度為1的子數(shù)組和長(zhǎng)度大于1的子數(shù)組，如下圖

推算f[i]：

第一種情況：子數(shù)組長(zhǎng)度為1時(shí)

當(dāng)子數(shù)組的長(zhǎng)度為1時(shí)，也是有兩種情況的，分別是nums[i]大于0和nums[i]<0的情況。

當(dāng)nums[i]>0時(shí)，此時(shí)f[i]=1，當(dāng)nums[i]<0時(shí)，此時(shí)f[i]=0?

當(dāng)子數(shù)組的長(zhǎng)度大于1時(shí)，也是有兩種情況的，分別是nums[i]大于0和nums[i]<0的情況。

當(dāng)nums[i]>0時(shí)，此時(shí)首先要知道以i-1位置為結(jié)尾的所有子數(shù)組中乘積為正數(shù)的最長(zhǎng)長(zhǎng)度，根據(jù)f[i]的狀態(tài)表示，可以用f[i-1]來表示以i-1位置為結(jié)尾的所有子數(shù)組中乘積為正數(shù)的最長(zhǎng)長(zhǎng)度，此時(shí)，f[i]=f[i-1]+1

當(dāng)nums[i]<0時(shí)，因?yàn)閒[i]表示以i位置為結(jié)尾的所有子數(shù)組中乘積為正數(shù)的最長(zhǎng)長(zhǎng)度，因?yàn)檎龜?shù)*負(fù)數(shù)等于負(fù)數(shù)，所以此時(shí)還要知道以i-1為位置為結(jié)尾的所有子數(shù)組中乘積為負(fù)數(shù)的最長(zhǎng)長(zhǎng)度，所以此時(shí)還要另外設(shè)計(jì)一個(gè)狀態(tài)表示，用g[i]表示以i位置為結(jié)尾的所有子數(shù)組中乘積為負(fù)數(shù)的最長(zhǎng)長(zhǎng)度，此時(shí)就可以用g[i-1]來表示以i-1為位置為結(jié)尾的所有子數(shù)組中乘積為負(fù)數(shù)的最長(zhǎng)長(zhǎng)度，此時(shí)慣性思維就直接讓f[i]=g[i-1]+1了，但是這樣是不對(duì)的，如果g[i-1]==0，說明i位置前面的數(shù)字全是正數(shù)相乘，如果此時(shí)nums[i]<0的話，此時(shí)f[i]是等于0的，因?yàn)樽訑?shù)組都要包含i位置這個(gè)數(shù)據(jù)，如果按照上面的f[i]=g[i-1]+1，此時(shí)計(jì)算的f[i]是等于1的，所以此時(shí)的狀態(tài)轉(zhuǎn)移方程為：

f[i] = g[i-1]==0 ? 0 : g[i-1]+1

分析總結(jié)圖如下

所以此時(shí)在推算狀態(tài)轉(zhuǎn)移方程時(shí)，也要分為2中情況

第一種情況：nums[i]>0時(shí)，此時(shí)f[i]=Math.max(1,f[i-1]+1)，可以簡(jiǎn)化成f[i]=f[i-1]+1

第二種情況：nums[i]<0時(shí)，此時(shí)f[i]=Math.max(0,g[i-1]==0?0:g[i-1]+1) ，可以簡(jiǎn)化成f[i]=g[i-1]==0?0:g[i-1]+1

如下圖：

推算g[i]:

此時(shí)推算g[i]的過程和上面一模一樣，有一個(gè)細(xì)節(jié)不同

不同之處：

當(dāng)子數(shù)組的長(zhǎng)度>1時(shí)，此時(shí)推算g[i]時(shí)，有一個(gè)nums[i]>0的情況，此時(shí)可能慣性思維直接推出g[i]=g[i-1]+1，但是這是不對(duì)的，如果此時(shí)g[i-1]==0，說明前面都是正數(shù)相乘，此時(shí)再加上nums[i]>0，此時(shí)g[i]是等于0的，如果根據(jù)上面的g[i]=g[i-1]+1，此時(shí)計(jì)算的g[i]是等于1的，所以此時(shí)g[i]=g[i-1]==0?0:g[i-1]+1

根據(jù)上面的分析總結(jié)圖，推出g[i]的狀態(tài)轉(zhuǎn)移方程：

第一種情況：nums[i]>0時(shí)，此時(shí)g[i]=Math.max(0,g[i-1]==0?0:g[i-1]+1) ，可以簡(jiǎn)化成g[i]=g[i-1]==0?0:g[i-1]+1

第二種情況：nums[i]<0時(shí)，此時(shí)g[i]=Math.max(1,f[i-1]+1)，可以簡(jiǎn)化成f[i]=f[i-1]+1

3.初始化

這里依舊是選擇多創(chuàng)建一部分空間實(shí)現(xiàn)初始化

根據(jù)一個(gè)表分析即可，此時(shí)用g表來分析，此時(shí)g[1]初始化有兩種情況，當(dāng)nums[0]<0時(shí)，要將g[1]初始化為1，所以根據(jù)g[i]狀態(tài)轉(zhuǎn)移方程小于0的情況，此時(shí)要將g[0]初始化為0，當(dāng)nums[0]>0時(shí)，此時(shí)要將g[i]初始化為0，根據(jù)g[i]狀態(tài)轉(zhuǎn)移方程大于0的情況，此時(shí)要將f[0]初始化為0

第二個(gè)注意事項(xiàng)：注意下標(biāo)的映射關(guān)系

4.填表順序

從左往右同時(shí)填兩個(gè)表即可

5.返回值

返回f表中的最大值

代碼實(shí)現(xiàn)：

class Solution {public int getMaxLen(int[] nums) {int n=nums.length;int[] f=new int[n+1];int[] g=new int[n+1];f[0]=0;g[0]=0;int ret=Integer.MIN_VALUE;for(int i=1;i<n+1;i++){int x=nums[i-1];if(x>0){f[i]=f[i-1]+1;g[i]=g[i-1]==0?0:g[i-1]+1;}else if(x<0){f[i]=g[i-1]==0?0:g[i-1]+1;g[i]=f[i-1]+1;}ret=Math.max(ret,f[i]);}return ret;}
}

5.等差數(shù)列劃分

題目鏈接：413. 等差數(shù)列劃分 - 力扣（LeetCode）?

題目解析：返回nums數(shù)組中能夠成等差數(shù)列的子數(shù)組的個(gè)數(shù)?

算法講解：動(dòng)態(tài)規(guī)劃?

1.狀態(tài)表示：經(jīng)驗(yàn)+題目要求

由于題目要求返回nums數(shù)組中所有為等差數(shù)列的子數(shù)組的個(gè)數(shù)，此時(shí)就可以將狀態(tài)表示：

dp[i]表示：以i位置元素為結(jié)尾的所有子數(shù)組中能構(gòu)成等差數(shù)列的個(gè)數(shù)?

2.狀態(tài)轉(zhuǎn)移方程

首先要知道如果[a,b,c,d]這4個(gè)數(shù)構(gòu)成等差數(shù)列，如果此時(shí)c,d,e也能構(gòu)成等差數(shù)列，此時(shí)a.b,c,d,e也是能構(gòu)成等差數(shù)列的

現(xiàn)在開始分析，因?yàn)闃?gòu)成等差數(shù)列至少需要3個(gè)元素，所以分析時(shí)要至少以3個(gè)元素開始分析，如下圖

假設(shè)此時(shí)這3個(gè)元素是a，b，c，此時(shí)分析這三個(gè)數(shù)能否構(gòu)成等差數(shù)列

第一種情況：如果a，b，c這3個(gè)數(shù)構(gòu)成等差數(shù)列，也就是nums[i]-nums[i-1]==nums[i-1]-nums[i-1]，此時(shí)如果要求出dp[i]，首先就要知道以a，b為結(jié)尾的所有子數(shù)組中能構(gòu)成等差數(shù)列的子數(shù)組個(gè)數(shù)，以a，b結(jié)尾就是以b結(jié)尾，此時(shí)就可以用dp[i-1]來表示以b結(jié)尾的所有子數(shù)組中能構(gòu)成等差數(shù)列的個(gè)數(shù)，此時(shí)dp[i]就是在dp[i-1]的基礎(chǔ)上加1即可，這里的加1是指dp[i-1]中沒有包含a,b,c這種情況，如下圖

第二種情況：a，b，c這三個(gè)元素不構(gòu)成等差數(shù)列，如果a，b，c這三個(gè)元素不夠成等差數(shù)列，那么此時(shí)a，b，c，d就也不會(huì)構(gòu)成等差數(shù)列了，此時(shí)直接讓dp[i]=0即可

3.初始化

因?yàn)闃?gòu)成等差數(shù)列至少需要3個(gè)數(shù)據(jù)，所以要將dp[0]和dp[1]都初始化為0

4.填表順序

從左往右填表即可

5.返回值

因?yàn)橐祷啬軜?gòu)成等差數(shù)列的子數(shù)組個(gè)數(shù)，所以要用一個(gè)ret來記錄

代碼實(shí)現(xiàn)：

class Solution {public int numberOfArithmeticSlices(int[] nums) {int n=nums.length;if(n==1||n==2) return 0;int[] dp=new int[n];int ret=0;for(int i=2;i<n;i++){if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){dp[i]+=dp[i-1]+1;ret+=dp[i];}else{dp[i]=0;}}return ret;}
}

6.最長(zhǎng)湍流子數(shù)組?

題目鏈接：978. 最長(zhǎng)湍流子數(shù)組 - 力扣（LeetCode）?

題目解析：啥事湍流子數(shù)組呢？數(shù)組中的數(shù)據(jù)呈現(xiàn)下面的趨勢(shì)就是湍流數(shù)組，如下圖

算法講解：動(dòng)態(tài)規(guī)劃

1.狀態(tài)表示：經(jīng)驗(yàn)+題目要求

首先想到的狀態(tài)表示肯定是：

dp[i]表示：以i位置為結(jié)尾的所有子數(shù)組中，最長(zhǎng)湍流子數(shù)組的長(zhǎng)度

根據(jù)下面的分析，推出兩個(gè)狀態(tài)表示：

f[i]表示：以i位置為結(jié)尾的所有子數(shù)組中，最后呈現(xiàn)上升趨勢(shì)狀態(tài)下的最長(zhǎng)湍流子數(shù)組的長(zhǎng)度?

g[i]表示：以i位置為結(jié)尾的所有子數(shù)組中，最后呈現(xiàn)下降趨勢(shì)狀態(tài)下的最長(zhǎng)湍流子數(shù)組的長(zhǎng)度?

2.狀態(tài)轉(zhuǎn)移方程：

此時(shí)推算dp[i]時(shí)，由于找到子數(shù)組要是湍流子數(shù)組，所以此時(shí)nums[i-1]和nums[i]組成的趨勢(shì)有上升和下降的兩種情況，如下圖

所以此時(shí)單獨(dú)靠一個(gè)狀態(tài)表示是不能夠解決問題，還要添加兩個(gè)狀態(tài)表示f[i]和g[i]?

此時(shí)推算f[i]，依舊是上圖的三種情況來分析f[i]

第一種情況：nums[i]>nums[i-1]

當(dāng)nums[i]>nums[i-1]，最后一段是上升的趨勢(shì)，由于要找的湍流子數(shù)組，所以此時(shí)首先要找出以i-1位置為結(jié)尾的所有子數(shù)組中，最后呈現(xiàn)下降趨勢(shì)狀態(tài)的最長(zhǎng)湍流子數(shù)組的長(zhǎng)度，根據(jù)g[i]的狀態(tài)表示，可以用g[i-1]來表示，所以此時(shí)f[i]=g[i-1]+1

第二種情：nums[i]<nums[i-1]

當(dāng)nums[i]<nums[i-1]，此時(shí)最后一段呈現(xiàn)下降趨勢(shì)，不符合f[i]的狀態(tài)表示，所以讓nums[i]單獨(dú)成為一個(gè)湍流子數(shù)組，則此時(shí)f[i]=1

第三種情況：nums[i]==nums[i-1]

當(dāng)nums[i]==nums[i-1]，此時(shí)最后一段呈現(xiàn)沒有變化的趨勢(shì)，此時(shí)不符合f[i]的狀態(tài)表示，所以讓nums[i]單獨(dú)成為一個(gè)湍流子數(shù)組，此時(shí)f[i]=1

接著來推算g[i]，還是上面這三種情況來分析

第一種情況：nums[i]>nums[i-1]

當(dāng)nums[i]<nums[i-1]，最后一段是下降的趨勢(shì)，由于要找的湍流子數(shù)組，所以此時(shí)首先要找出以i-1位置為結(jié)尾的所有子數(shù)組中，最后呈現(xiàn)上升趨勢(shì)狀態(tài)的最長(zhǎng)湍流子數(shù)組的長(zhǎng)度，根據(jù)f[i]的狀態(tài)表示，可以用f[i-1]來表示，所以此時(shí)g[i]=f[i-1]+1

第二種情：nums[i]>nums[i-1]

當(dāng)nums[i]>nums[i-1]，此時(shí)最后一段呈現(xiàn)上升趨勢(shì)，不符合g[i]的狀態(tài)表示，所以讓nums[i]單獨(dú)成為一個(gè)湍流子數(shù)組，則此時(shí)g[i]=1

第三種情況：nums[i]==nums[i-1]

當(dāng)nums[i]==nums[i-1]，此時(shí)最后一段呈現(xiàn)沒有變化的趨勢(shì)，此時(shí)不符合g[i]的狀態(tài)表示，所以讓nums[i]單獨(dú)成為一個(gè)湍流子數(shù)組，此時(shí)g[i]=1

3.初始化?

此時(shí)可以先將f表和g表都初始化為1，因?yàn)樽顗牡那闆r就是1，還有一個(gè)好處，就是寫代碼時(shí)就不用考慮f[i]和g[i]等于1的情況了

4.填表順序

從左往右同時(shí)填兩個(gè)表即可

5.返回值

返回f表和g表中的最大值

代碼實(shí)現(xiàn)?

class Solution {public int maxTurbulenceSize(int[] nums) {int n=nums.length;int[] f=new int[n];int[] g=new int[n];for(int i=0;i<n;i++){f[i]=1;g[i]=1;}int ret=1;for(int i=1;i<n;i++){if(nums[i]>nums[i-1]){f[i]=g[i-1]+1;}else if(nums[i]<nums[i-1]){g[i]=f[i-1]+1;}ret=Math.max(ret,Math.max(f[i],g[i]));}return ret;}
}

7.單詞拆分?

題目鏈接：139. 單詞拆分 - 力扣（LeetCode）?

題目解析：判斷字符串s能不能有字典中的字符串拼接出來，字典中的字符串可以重復(fù)使用

算法講解：動(dòng)態(tài)規(guī)劃

1.狀態(tài)表示：經(jīng)驗(yàn)+題目要求

在這道題因?yàn)橐袛嘧址懿荒苡勺值渲械淖址唇映鰜?#xff0c;可以這樣定義狀態(tài)表示：

dp[i]表示：[0，i]區(qū)間內(nèi)的字符串，能否被字典中的字符串拼接而成

當(dāng)dp[i]==true時(shí)，說明可以由字典中的字符串拼接而成

當(dāng)dp[i]==false時(shí)，說明不可以由字典中的字符串拼接而成?

2.狀態(tài)轉(zhuǎn)移方程

根據(jù)最后一個(gè)單詞的情況來分析問題，此時(shí)可以是字符串中的最后一個(gè)字符作為單獨(dú)一個(gè)單詞來作為最后一個(gè)單詞，也可以是最后一個(gè)字符和前面的字符合并成為一個(gè)單詞作為最后一個(gè)單詞，如下圖

此時(shí)，子字符串就可以分為兩種情況了，也就是前面一個(gè)單詞和最后一個(gè)單詞，如下圖

此時(shí)，要向判斷dp[i]是true還是false，也就是判斷能不能由字典中的字符串拼接而成，就需要判斷前面一個(gè)單詞能不能由字典中的字符串拼接而成，和最后一個(gè)單詞存不存在于字典中，為了方便敘述，為了方便敘述，用一個(gè)變量j來表示最后一個(gè)單詞的起始位置（此處的j是小于等于i且大于等于0的），要想則dp[j-1]就是[0，j-1]區(qū)間內(nèi)的字符串能否由字典中的單詞拼接而成，如果dp[j-1]==true且最后一個(gè)單詞存在于字典中，則dp[i]就等于true，否則dp[i]就等于false，如下圖

3.初始化

為了方便初始化，將創(chuàng)建虛擬節(jié)點(diǎn)來實(shí)現(xiàn)初始化，此時(shí)需要注意虛擬節(jié)點(diǎn)填的值要保證后面填表正確和下標(biāo)映射的問題

下標(biāo)映射這里，可以往s的前面加一個(gè)空格，就可以避免下標(biāo)映射的問題了

4.填表順序

從左往右填表即可

5.返回值

返回dp[n]即可

代碼實(shí)現(xiàn)

為什么第二個(gè)循環(huán)里面是j>=1呢？因?yàn)榍懊嫱鵶前面增加了一個(gè)空格，讓s的長(zhǎng)度增加了1，所以此時(shí)的1就是原本的0?

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> hash=new HashSet<>(wordDict);int n=s.length();boolean[] dp=new boolean[n+1];dp[0]=true;s=" "+s;for(int i=1;i<n+1;i++){for(int j=i;j>=1;j--){if(dp[j-1]&&hash.contains(s.substring(j,i+1))){dp[i]=true;break;}}}return dp[n];}
}

8.環(huán)繞字符串中唯一的子字符串?

題目鏈接：467. 環(huán)繞字符串中唯一的子字符串 - 力扣（LeetCode）?

題目解析：計(jì)算并返回字符串s中有多少非空不同子串在base中出現(xiàn)

算法講解：動(dòng)態(tài)規(guī)劃

1.狀態(tài)表示：經(jīng)驗(yàn)+題目要求

因?yàn)轭}目要求返回字符串s中有多少非空不同子串在base中出現(xiàn)，根據(jù)經(jīng)驗(yàn)，可以這樣定義狀態(tài)表示：

dp[i]表示：以i位置元素結(jié)尾的非空不同子串中，有多少個(gè)在base中出現(xiàn)?

2.狀態(tài)轉(zhuǎn)移方程

因?yàn)槲覀円谧址畇中找子串，所以此時(shí)以i位置字符結(jié)尾的子串會(huì)有兩種情況，分別是長(zhǎng)度為1和長(zhǎng)度大于1的情況，如下圖

所以此時(shí)推算dp[i]時(shí)，也要分為兩種情況：

第一種情況：子串的長(zhǎng)度為1?

當(dāng)子串為1時(shí)，也就是ch[i]單獨(dú)一個(gè)字符作為子串，此時(shí)是一定會(huì)在base中出現(xiàn)的，所以此時(shí)dp[i]=1

第二種情況：子串的長(zhǎng)度大于1

當(dāng)子串的長(zhǎng)度大于1時(shí)，如果要計(jì)算dp[i]，就要先知道以i-1位置為結(jié)尾的非空子串，有多少個(gè)出現(xiàn)在base中，根據(jù)dp[i]的狀態(tài)表示，可以dp[i-1]來表示

那如何判斷以i位置為結(jié)尾的非空子串是出現(xiàn)在base中的呢？

此時(shí)無非就兩種情況，當(dāng)ch[i]和ch[i-1]在26個(gè)小寫的英文中是相鄰的，也就是ch[i-1]+1=ch[i]，因?yàn)閎ase是連續(xù)字符串，所以還要考慮ch[i-1]=='z'和ch[i]=='a'的情況，當(dāng)這兩種情況，有一種符合時(shí)，就代表在base中出現(xiàn)

3.初始化

此時(shí)可以先將dp表中的全部數(shù)據(jù)初始化為1，因?yàn)榇藭r(shí)的最壞情況就是1，這樣還有一個(gè)好處，就是寫代碼時(shí)，就不用考慮dp[i]==1的情況了

4.填表順序

從左往右填dp表即可

5.返回值

注意返回時(shí)是要求不同子串的個(gè)數(shù)，所以還要去重

以s="aca"為例，當(dāng)i等于0時(shí)，此時(shí)子串就是"a"，此時(shí)dp[0]=1，當(dāng)i等于3時(shí)，此時(shí)子串的情況就有"a"，"ca"，和"aca"的情況，此時(shí)計(jì)算dp[3]時(shí)，有計(jì)算了一次子串為"a"的情況，所以此時(shí)要去重

去重策略：

根據(jù)上面的分析，"aca"的情況就已經(jīng)包含了"a"的情況，所以在計(jì)算ret時(shí)，相同字符結(jié)尾的dp值，去最大的那一個(gè)即可

如何實(shí)現(xiàn)去重策略：

定義一個(gè)大小為26的int數(shù)組，遍歷dp表，將相同字符結(jié)尾的dp值中較大的放進(jìn)數(shù)組即可

代碼實(shí)現(xiàn)：

class Solution {public int findSubstringInWraproundString(String s) {char[] ch=s.toCharArray();int n=ch.length;int[] dp=new int[n];for(int i=0;i<n;i++) dp[i]=1;for(int i=1;i<n;i++){if(ch[i-1]+1==ch[i] || ch[i-1]=='z'&&ch[i]=='a'){dp[i]+=dp[i-1];}}//去重int[] hash=new int[26];for(int i=0;i<n;i++)hash[ch[i]-'a']=Math.max(hash[ch[i]-'a'],dp[i]);//計(jì)算返回結(jié)果int ret=0;for(int i=0;i<26;i++)ret+=hash[i];return ret;}
}