劍指offer42-連續子陣列的最大和（動態規劃）
- 1 題目描述
- 2 解題思路
- 3 代碼實作
1 題目描述
輸入一個整型陣列，陣列中的一個或連續多個整陣列成一個子陣列，求所有子陣列的和的最大值，
要求時間復雜度為O(n)，
示例：
輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子陣列 [4,-1,2,1] 的和最大，為 6，
2 解題思路
因為涉及到動態路徑以及最優解的問題，因此首先想到使用動態規劃來解答，那么本題的關鍵點就在于正確寫出轉移方程如下：
步驟：
- 建立一個和數字長度一致的dp表，
- 計算出陣列中每個元素對應的dp值(當前元素結尾的子串的最大和)，
- 找出dp表中的最大值，即為本題所求的值，
3 代碼實作
class Solution {
public static void main(String[] args){
System.out.println("請輸入一個整數型陣列，以空格隔開：");
Scanner sc = new Scanner(System.in);
//定義字串陣列
String[] nums = null;
//切分字串，并將切分后的字串保存在字串陣列中
nums = sc.nextLine().split(" ");
int[] num = new int[nums.length];
for(int i = 0; i < num.length; i++){
//String轉Integer基本型別
num[i] = Integer.valueOf(nums[i]);
}
System.out.println(maxsubArray(num));
}
public int maxSubArray(int[] nums) {
//定義dp表,長度和陣列相等
int[] dp = new int[nums.length];
dp[0]=nums[0];
//計算dp表
for(int j = 1;j<nums.length;j++){
if(dp[j-1]>0){
dp[j] = dp[j-1]+nums[j];//轉移方程
}else{
dp[j] = nums[j];//轉移方程
}
}
//求最大值
int max = Integer.MIN_VALUE;
for(int i = 0;i<dp.length;i++){
if(dp[i]>max)
max = dp[i];
}
return max;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271896.html
標籤：其他
上一篇：植物大戰僵尸如何修改金幣和關卡
下一篇：PHP和JAVA的區別