Maximum Subarray (E)
題目
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
題意
找到給定陣列中的一個子陣列，使其和最大，
思路
與連續區間有關的問題很容易想到使用動態規劃：dp[i]代表以nums[i]為結尾的各個子陣列中的最大和，可以得到運算式 \(dp[i]=max(nums[i],\ dp[i-1]+nums[i])\)，(當然可以直接把原陣列當dp陣列用，但為了使代碼易讀還是新建了dp陣列)
下面介紹一種直接遍歷累加的方法：每次將要累加當前值時，先判斷之前已經累加的和是否為負數，如果為負數，當前值加上一個負數只會比自身更小，不如不加，直接重置之前的累加和為0；如果為正數，則可以直接在當前值上加上累加和，這種方法本質上和動態規劃是一樣的，
分治法：將求當前陣列中的最大子陣列和這一問題分解為，求出左半邊陣列中的最大子陣列和leftMax、右半邊陣列中的最大子陣列和rightMax、包含左右分割點的中間陣列中的最大子陣列和midMax，這三者中的最大值即為問題的解，復雜度為\(O(NlogN)\)，
代碼實作
Java
動態規劃
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
int max = nums[0];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
max = Math.max(max, dp[i]);
}
return max;
}
}
遍歷累加
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int sum = nums[0];
for (int i = 1; i < nums.length; i++) {
// 先判斷累加和是否為負數，是則重置為0
sum = Math.max(sum, 0);
sum += nums[i];
max = Math.max(max, sum);
}
return max;
}
}
分治法
class Solution {
public int maxSubArray(int[] nums) {
return divide(nums, 0, nums.length - 1);
}
private int divide(int[] nums, int left, int right) {
// 遞回邊界，陣列中只剩一個數
if (right == left) {
return nums[left];
}
int mid = (left + right) / 2;
// 中間陣列必須包含左陣列的右端點和右陣列的左端點
int leftSum = nums[mid], rightSum = nums[mid + 1];
int sum = 0;
int i = mid;
while (i >= left) {
sum += nums[i--];
leftSum = Math.max(leftSum, sum);
}
sum = 0;
i = mid + 1;
while (i <= right) {
sum += nums[i++];
rightSum = Math.max(rightSum, sum);
}
int midMax = leftSum + rightSum;
int leftMax = divide(nums, left, mid);
int rightMax = divide(nums, mid + 1, right);
return Math.max(midMax, Math.max(leftMax, rightMax));
}
}
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function (nums) {
let max = nums[0]
let sum = nums[0]
for (let i = 1; i < nums.length; i++) {
sum = sum < 0 ? nums[i] : sum + nums[i]
max = Math.max(sum, max)
}
return max
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/31067.html
標籤：其他