文章目錄
- 動態規劃解題套路
- 四步法
- 劍指offer 42連續子陣列的最大和
- 題目
- 分析
- 代碼
動態規劃解題套路
很多面試筆試題目涉及到的大部分都是DP的題目，這部分試題靈活性較高，而其中最重要的就是找出狀態轉移方程，方程找的好相當于成功了一半，
這類題目需要不斷地刷題來總結套路，總結就是多做題多總結多分析，
四步法
[0] 定義特殊情況，
這部分的主要任務就是把特殊情況先列明解決掉，比如陣列為null時候，直接return .....
【這一步有時候題目沒有特殊情況的時候是可以省略的】
[1] 定義dp陣列
這一步是定義dp陣列，而dp陣列的含義一般為題目所求的問題
即你想求什么問題，就定義dp陣列的含義是什么
[2] 找出狀態轉移方程
真正的大頭就是 == 狀態轉移方程 == 的查找了，
一般是將題目所求的大問題分解成小問題去尋找之間的關系，
題目要求dp[n]，我們可以向高中數學一樣，列出dp[n-1],dp[n-2].........觀察他們之間的關系，
一般這里都會用到for回圈
tips:我自己做題的一個技巧
前期不熟悉的時候很難觀察出各項之間的關系，可以舉例子，每一項都計算出具體的數字，觀察每一項之間的關系
這個對于新手的幫助是挺大的，
【注意的一點是】狀態轉移方程一定要體現出前后幾項之間的關系
[3] base case
這一步就是初始條件的定義，比如dp[0]是什么，dp[1]是什么，定義幾個初始條件
具體定義情況視題目而定，
以上即為做動態規劃題目的幾個套路，按部就班來做一般思路都會有的，剩下的就是多做題多總結了，
劍指offer 42連續子陣列的最大和
題目
輸入一個整型陣列，陣列中的一個或連續多個整陣列成一個子陣列，求所有子陣列的和的最大值，
要求時間復雜度為O(n)，
示例1:
輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子陣列 [4,-1,2,1] 的和最大，為 6，
提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
分析
下面就是根據上面總結的四步法進行這道題目的分析以及求解，
-
【0】 特殊情況的討論 ，
這道題由于【1 <= arr.length <= 10^5】的限制，即陣列不為null，所以這一步可以省略， -
【1】 定義dp陣列，
題目所求為連續子陣列的最大和，則定義一個dp陣列，長度和原陣列一樣，每個位置的元素的意義是以當前元素為結尾的子陣列的最大和，即dp[ ]陣列存盤 的是每個元素的子陣列的最大和，那么最終結果就是遍歷dp陣列回傳它的max值即可， -
[tips]：注意這里的子陣列包括元素本身，即元素本身也可作為一個子陣列，這個情況是我做題沒考慮的，提交leetcode的時候才發現有點bug，要把這種情況也加進去比較討論
-
【2】狀態轉移方程的確立，
狀態轉移方程要體現前后者的關系，以n結尾的子陣列的和等于以n-1結尾的子陣列的最大和與第n-1個元素對比后的Max 加上本身第n個元素，
即dp[n] = Math.max(dp[n-1]，nums[n-1]) +nums[n] -
【3】 base case
dp[0]=nums[0].即dp陣列最開始的元素為nums陣列第0個元素，就是本身，
代碼如下，代碼上面也加了注解，方便閱讀，
【如果題目要求書寫ACM模式，可以看我下一篇文章】
tips：ACM模式解法
代碼
class Solution {
public int maxSubArray(int[] nums) {
int n=nums.length;
//1.定義dp陣列
int[] dp=new int[n];
//3.base case
dp[0]=nums[0];
//2.狀態轉移方程
for(int i=1;i<n;i++){
//可以通過具體的數字列明觀察各個數之間的關系
//得出狀態轉移方程，這個狀態轉移方程一定要能夠體現出來i項和i-1項之間的區別，
dp[i]=Math.max( (Math.max(dp[i-1],nums[i-1]) +nums[i]), nums[i] );
//這里還要再添加和它本身的一個對比，比如[-2,1],最大子序列和為它本身即1.
}
//遍歷dp陣列找出max元素
int max=dp[0];
for(int i=1;i<n;i++){
if(dp[i]>max){
max=dp[i];
}
}
return max;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272572.html
標籤：其他
下一篇：游戲玩家的程式猿之路