劍指 Offer 42. 連續子陣列的最大和
題目鏈接：
https://leetcode-cn.com/problems/maximum-subarray/solution/
代碼連接
https://gitee.com/aninstein/HappyJava/blob/master/learn_java/src/leetcode/offer100/arrays/EasyMaxSubArraySum.java
package leetcode.offer100.arrays;
/**
* 題目：劍指 Offer 42. 連續子陣列的最大和
* 題目鏈接：https://leetcode-cn.com/problems/maximum-subarray/solution/
*
* 1. 暴力解法
* 2. 動態規劃
* 3. 分治法，這個分治方法類似于「線段樹求解最長公共上升子序列問題」的 pushUp 操作（太難了這里不寫了），具體看題解：https://leetcode-cn.com/problems/maximum-subarray/solution/
*
*/
public class MaxSubArraySum {
/**
* 暴力解法
* @param nums
* @return
*/
public static int maxSubArrayViolence(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int res = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
int tempSum = 0;
for (int j = i; j < len; j++) {
tempSum += nums[j];
if (tempSum > res) {
res = tempSum;
}
}
}
return res;
}
/**
* 動態規劃
* dp[i]陣串列示以i結尾的子陣列最大和
*
* 我們要求的結果是res = max(dp[0...len])
* 對于i-1狀態能不能夠轉移到i狀態，取決于nums[i]加入的情況是不是比nums[i]本身大
* 即因為dp[i-1]已經是第i-1結尾的子陣列最大和，對于nums[i]來說，只有：
* 1. 自成一段
* 2. 與dp[i-1]一起構成一段
* 則有：
* dp[i] = max(nums[i], dp[i-1] + nums[i])
*
* @param nums
* @return
*/
public static int maxSubArrayDp(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = nums.length;
int[] dp = new int[len];
int res = nums[0]; // 第一個資料
dp[0] = nums[0];
for (int i = 1; i < len; i++) {
dp[i] = Math.max(nums[i], dp[i-1] + nums[i]);
if (dp[i] > res) {
res = dp[i];
}
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/286482.html
標籤：其他