LeetCode [53] Maximum Subarray

 53. Maximum Subarray

Easy

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

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.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-2147483647]
Output: -2147483647

 

Constraints:

• 1 <= nums.length <= 2 * 104
• -231 <= nums[i] <= 231 - 1

//C++ class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 0); int ret = INT_MIN; for(int i=0; i<n; ++i){ if(i==0){ dp[i] = nums[i]; }else{ dp[i] = max(dp[i-1]+nums[i], nums[i]); } ret = max(ret, dp[i]); } return ret; } }; class Solution { public: int maxSubArray(vector<int>& nums) { int max_ending_here = INT_MIN; int max_so_far = INT_MIN; for(auto n:nums){ if(max_ending_here<0) max_ending_here = 0; max_ending_here += n; max_so_far = max(max_so_far, max_ending_here); } return max_so_far; } }; class Solution { public: int maxSubArray(vector<int>& nums, int l, int m, int r){ int sum = 0; int left = INT_MIN; for(int i=m; i>=l; --i){ sum += nums[i]; left = max(left, sum); } sum = 0; int right = INT_MIN; for(int i=m+1; i<=r; ++i){ sum += nums[i]; right = max(right, sum); } return left+right; } int maxSubArray(vector<int>& nums, int l, int r){ if(l>r) return 0; if(l==r) return nums[l]; int m = (l+r)/2; int left = maxSubArray(nums, l, m); int right = maxSubArray(nums, m+1, r); int cross = maxSubArray(nums, l, m, r); return max(left, max(right, cross)); } int maxSubArray(vector<int>& nums) { return maxSubArray(nums, 0, nums.size()-1); } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int maxSum = Integer.MIN_VALUE; int[] dp = new int[n];//local optimal ending(including) at i for(int i=0; i<n; ++i){ dp[i] = nums[i]; if(i>0 && dp[i]<dp[i-1]+nums[i]){ dp[i] = dp[i-1]+nums[i]; } maxSum = Math.max(maxSum, dp[i]); } return maxSum; } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int maxSum = Integer.MIN_VALUE; int prev = 0;//local optimal for(int i=0; i<n; ++i){ int cur = nums[i]; if(i>0 && cur<prev+nums[i]){ cur = prev+nums[i]; } maxSum = Math.max(maxSum, cur); prev = cur; } return maxSum; } }

YMSF

Given an array containing only 0 and 1s, find the best subarray to perform a single flip operation. The goal is that: after the flip, number of 1s should  be the maximum.

Flip operation means that you will convert all 0 to 1, and all 1 to 0 in that array.

You can skip flipping if you think it is not worth doing the flip.

Return the maximum number of 1s after you do the flip.

队友还是用的prefix sum再找区间最大的差值，面试官说可以O(1)空间，作为homework。

Follow-up: what if it is a 2D array?

第二轮，考虑flip 0的收益是1，flip 1的收益是-1，问题转化为【求一个element是1或者-1的array的max subarray sum】，直接slide window就可以了。等价于leetcode 53。（一个小区别是这里可以选择empty subarray）

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

package Flip01; public class Main { public static void main(String[] args) { Solution sol = new Solution(); int[] arr = new int[]{0,0,1,0,0}; int r = sol.getMax1(arr); System.out.println(r); } } class Solution{ int getMax1(int[] arr){ int n = arr.length; int max1s = 0; int prevFlip = 1-arr[0]; int prevNotFlip = arr[0]; for(int i=1; i<n; ++i){ int curNotFlip = Math.max(arr[i], prevNotFlip + arr[i]); int curFlip = Math.max(1-arr[i], prevFlip + 1-arr[i]); max1s = Math.max(max1s, Math.max(curNotFlip, curFlip)); prevFlip = curFlip; prevNotFlip = curNotFlip; } return max1s; } }