目錄

一、乘積最大數(shù)組

二、乘積為正數(shù)的最長子數(shù)組長度

三、等差數(shù)列劃分

四、最長湍流子數(shù)組

---

心得：

最重要的還是狀態(tài)表示，我們需要根據(jù)題的意思，來分析出不同的題，不同的情況，來分析需要多少個狀態(tài)

一、乘積最大數(shù)組

乘積最大數(shù)組

1.狀態(tài)表示

dp[i]:到達i位置的最大乘積子數(shù)組。

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

dp[i]=Math.max(dp[i-1]*p[i],dp[i-1]);

問題：不能通過簡單的最大值來填表，因為他的這個存在負負得正的情況，但是他其實一共乘法分為兩種情況

正*正為正 最大值

正*負為負 最小值

負*負為正 最大值

狀態(tài)表示更改為

f[i]:到達i位置，最大的乘積

g[i]:到達i位置，最小的乘積

所以狀態(tài)轉(zhuǎn)移方程也需要去變

?f[i]=Math.max(nums[i],Math.max(f[i-1]*nums[i],g[i-1]*nums[i]));
?g[i]=Math.min(nums[i],Math.min(f[i-1]*nums[i],g[i-1]*nums[i]));

3.初始化

f[0]=g[0]=nums[0]

4.填表順序

從左到右

5.返回值

class Solution {public int maxProduct(int[] nums) {int m=nums.length;//f為最大乘積和//g為最小乘積和int[]f=new int[m];int[]g=new int[m];f[0]=g[0]=nums[0];for(int i=1;i<m;i++){//f[i]狀態(tài)表示f[i]=Math.max(nums[i],Math.max(f[i-1]*nums[i],g[i-1]*nums[i]));g[i]=Math.min(nums[i],Math.min(f[i-1]*nums[i],g[i-1]*nums[i]));}
int ret =-0x3f3f3f3f;for(int i=0;i<m;i++){ret=Math.max(ret,f[i]);}return  ret;}
}

二、乘積為正數(shù)的最長子數(shù)組長度

1.狀態(tài)表示

dp[i]=到達i位置乘積為正數(shù)的最長子數(shù)組長度

如果要確保乘積是正數(shù)，就需要我們上面那個乘積最大的數(shù)組的狀態(tài)表示

f[i]:以i元素為結(jié)尾位置，乘積為正數(shù)的長度

g[i]:以i位置為結(jié)尾位置，乘積為負數(shù)的長度

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

f[i]分為長度為1的情況和長度不為1的情況

長度為一的情況，還要區(qū)分是不是為正數(shù)

長度不為一的情況，看當(dāng)前i是正數(shù)還是負數(shù)

當(dāng)nums[i]<0的時候我們要想一件事情，假如說g[i-1]正好等于0，然而此時nums[i]<0，那么沒有正數(shù),最后的結(jié)果不就是等于0嗎。所以我們不能寫作當(dāng)nums[i]<0時候，f[i]=g[i-1]+1

3.初始化：

就單純的看nums[0]大于0還是小于0。 大于0那么f[0]就是1。小于0那么g[0]是1

4.填表順序：

從左到右

5返回值：返回值最大值

class Solution {public static int getMaxLen(int[] nums) {int m=nums.length;int f[]=new int[m];int g[]=new int[m];if(nums[0]>0){f[0]=1;}else if(nums[0]<0){g[0]=1;}for(int i=1;i<m;i++){//f[i]狀態(tài)表示if(nums[i]>0){f[i]=f[i-1]+1;if(g[i-1]==0){g[i]=0;}else{g[i]=g[i-1]+1;}}else if(nums[i]<0){if(g[i-1]==0){f[i]=0 ;}else{f[i]=g[i-1]+1;}g[i]=f[i-1]+1;}}int ret=0;for(int i=0;i<m;i++){ret=Math.max(ret,f[i]);}return ret;}}

三、等差數(shù)列劃分

1.狀態(tài)表示

dp[i]到達i位置等差數(shù)列的個數(shù)

2.狀態(tài)表示

如果nums[i]-nums[i-1]==nums[i-1]-nums[i-2]，那么他就構(gòu)成了一個三個數(shù)的等差數(shù)組,

如果他之前就是三個數(shù)的等差數(shù)組，加一個數(shù)也就可以組成一個四個數(shù)的等差數(shù)組

dp[i]=dp[i-1]+1 (多少個數(shù)的等差數(shù)組）然后假如說由3個變成4個，4-3也就是要加1即可，剩下的那個是在三個里面，換句話說，有上面那個判定條件，它是給你判定三個的，但是假如說你這個是4個，他就不會算在內(nèi)，所以4個的話就要多加1，五個就要多加一個4個，和一個五個，這樣慢慢的規(guī)律就是i-2即可（我的意思是假如是五個減去三個）

然后檢查三個的是不是一個等差數(shù)組

3.初始化:

小于3就是0

4.填表順序:

從左到右

5.返回值

return dp表中的最大值即可

class Solution {public static int numberOfArithmeticSlices(int[] nums) {int m=nums.length;int[]dp=new int[m];if(m<3){return 0;}int max=0;for(int i=2;i<m;i++){if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){dp[i]=dp[i-1]+1;if(i-2>0&&dp[i-1]!=0){dp[i]=dp[i]+i-2;}max=Math.max(dp[i-1],max);if(i-2>0&&dp[i-1]==0){dp[i]=max+1;}max=Math.max(dp[i],max);}}int ret=0;for(int i=0;i<m;i++){ret=Math.max(dp[i],ret);}return ret;}
}

四、最長湍流子數(shù)組

湍流數(shù)組用圖來表示就相當(dāng)于是

大概就是這種圖像的含義。*        *
*       *

1.狀態(tài)表示

dp[i]:到達i位置的最長湍流數(shù)組的長度

2.狀態(tài)表示

if(n%2==0){

假如nums[i]>nums[i+1]}

else{

nums[i]<nums[i+1]}

dp[i]=dp[i-1]+1

在這里我們發(fā)現(xiàn)一件事情，一個數(shù)組，他最多只能表示當(dāng)前的一種情況

但這個地方有三個狀態(tài)，所以不能說單靠一個表達湍流數(shù)組的狀態(tài)

所以我們決定使用f[i],g[i],來表示，前面兩種情況，最后那個是0

f[i]:表示在i位置，與i-1位置呈現(xiàn)下降趨勢,最長湍流數(shù)組長

g[i]:表示在i位置，與i-1位置呈現(xiàn)上升趨勢，最長湍流數(shù)組長

那么if(nums[i-1]>nums[i]){

f[i]=g[i-1]+1;

g[i]=1;

}

if(nums[i]<nums[i+1]){

f[i]=1；

g[i]=f[i-1]+1;

}

3.初始化

因為假如只有一個數(shù)字，那么湍流數(shù)組的長度是1，所以說，這個就默認(rèn)是1了。

從1到n

4.填表順序

從左到右

5.返回值

返回最大值

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