• ㊗️
• 大家
• offer
• 多多！

## Problem

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.


If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

## Code

class Solution {
public int maxSubArray(int[] nums) {

int max = nums[0];

int dp = nums[0];
for (int i = 1; i < nums.length; i++) {
// 如果dp<0就放弃dp
dp = Math.max(dp + nums[i], nums[i]);
max = Math.max(max, dp);
}

return max;
}
}


O(n) O(1)

class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0) return 0;

int res = nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];

for(int i = 1; i < nums.length; i++){
dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
res = Math.max(res, dp[i]);
}

return res;
}
}


divide and conquer 解法, 并不是最优解

class Solution {
private int[] numsArray;

public int maxSubArray(int[] nums) {
numsArray = nums;

// Our helper function is designed to solve this problem for
// any array - so just call it using the entire input!
return findBestSubarray(0, numsArray.length - 1);
}

private int findBestSubarray(int left, int right) {
// Base case - empty array.
if (left > right) {
return Integer.MIN_VALUE;
}

int mid = (left + right) / 2;
int curr = 0;
int bestLeftSum = 0;
int bestRightSum = 0;

// Iterate from the middle to the beginning.
for (int i = mid - 1; i >= left; i--) {
curr += numsArray[i];
bestLeftSum = Math.max(bestLeftSum, curr);
}

// Reset curr and iterate from the middle to the end.
curr = 0;
for (int i = mid + 1; i <= right; i++) {
curr += numsArray[i];
bestRightSum = Math.max(bestRightSum, curr);
}

// The bestCombinedSum uses the middle element and the best
// possible sum from each half.
int bestCombinedSum = numsArray[mid] + bestLeftSum + bestRightSum;

// Find the best subarray possible from both halves.
int leftHalf = findBestSubarray(left, mid - 1);
int rightHalf = findBestSubarray(mid + 1, right);

// The largest of the 3 is the answer for any given input array.
return Math.max(bestCombinedSum, Math.max(leftHalf, rightHalf));
}
}


time: nlog(n) space: log(n)

class Solution {

public List<Integer> maxSumWithK(int nums[], int k) {
int n = nums.length;
int maxSum[] = new int[n];
// 记录开始和结束的位置
int maxStart[] = new int[n];

maxSum[0] = nums[0];
int dp = nums[0];
int start = 0;
for (int i = 1; i < n; i++) {
if (dp < 0) {
maxStart[i] = i;
dp = nums[i];
} else {
dp += nums[i];
maxStart[i] = start;
}

maxSum[i] = dp;
}

// Sum of first k elements
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}

// sliding window
// 确保有k这么长的window, 然后看加上maxSum是否结果会变大
int result = sum;
int resStart = 0;
int resEnd = k;
for (int i = k; i < n; i++) {
// Compute sum of k elements ending with a[i].
// i ~ i + k
sum = sum + nums[i] - nums[i - k];

// Update result if required
if (sum > result) {
resStart = i - k;
resEnd = i;
result = sum;
}

if (sum + maxSum[i - k] > result) {
resStart = maxStart[i - k];
resEnd = i;
result = sum + maxSum[i - k];
}
}

List<Integer> res = new ArrayList<>();
for (int i = resStart; i < resEnd; i++) {