Comment on page
53.Maximum-Subarray
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.
- Time complexity : O(N) since it's one pass along the array
- Space complexity : O(1), since it's a constant space solution
public class Solution {
public int maxSubArray(ArrayList<Integer> nums) {
if (nums == null || nums.isEmpty()) return -1;
int sum = 0;
int maxSum = Integer.MIN_VALUE;
for (int num : nums) {
sum = Math.max(sum, 0);
sum += num;
// sum = Math.max(num, sum + num);
maxSum = Math.max(maxSum, sum);
}
return maxSum;
}
}
public class Solution{
public int maxSubArray(ArrayList<Integer> nums){
if (nums == null || nums.isEmpty()) return -1;
int sum = 0;
int minSum = 0;
int maxSub = Integer.MIN_VALUE;
for (int num : nums) {
minSum = Math.min(minSum, sum);
sum += num;
maxSub = Math.max(maxSub, sum - minSum);
}
return maxSub;
}
}
local[] 局部最小值 Math.max(nums.get(i), local[i - 1] + nums.get(i))global[] 全局最大值 Math.max(global[i - 1], local[i])public class Solution {
public int maxSubArray(ArrayList<Integer> nums){
int size = nums.size();
int[] local = new int[size];
int[] global = new int[size];
local[0] = nums.get(0);
global[0] = nums.get(0);
for (int i = 1; i < size; i++) {
// drop local[i - 1] < 0
local[i] = Math.max(nums.get(i), local[i - 1] + nums.get(i));
// update global with local
global[i] = Math.max(global[i - 1], local[i]);
}
return global[size - 1];
}
}
Time complexity :
O(NlogN). && Space complexity : O(logN)class Solution {
public int maxSubArray(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public int helper(int[] nums, int left, int right) {
if (left == right) return nums[left];
int middle = (left + right) / 2;
int leftSum = helper(nums, left, middle);
int rightSum = helper(nums, middle + 1, right);
int crossSum = crossSum(nums, left, right, middle);
return Math.max(Math.max(leftSum, rightSum), crossSum);
}
public int crossSum(int[] nums, int left, int right, int middle) {
if (left == right) return nums[left];
int leftSubSum = Integer.MIN_VALUE;
int currSum = 0;
for (int i = middle; i >= left; i--) {
currSum += nums[i];
leftSubSum = Math.max(leftSubSum, currSum);
}
int rightSubSum = Integer.MIN_VALUE;
currSum = 0;
for (int i = middle + 1; i <= right; i++) {
currSum += nums[i];
rightSubSum = Math.max(rightSubSum, currSum);
}
return leftSubSum + rightSubSum;
}
}
Last modified 2yr ago