Lintcode: Maximum Subarray

Given an array of integers, find a contiguous subarray which has the largest sum.

Have you met this question in a real interview? 

Yes

Example

Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Note

The subarray should contain at least one number.

Challenge

Can you do it in time complexity O(n)?

Reference:
Awesome Vedio!!
https://www.youtube.com/watch?v=ohHWQf1HDfU

Brute_Force:

try all subarrays from size 1 to n, and then compare to get maximum sum
cannot pass test
Time: O(n*n*n)
Space: O(1)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ int maxSubArray(vector<int> nums) { // write your code here if(nums.size() == 0) return 0; int sum = INT_MIN; for(int size = 1; size <= nums.size(); size++){ for(int start = 0; start < nums.size(); start++){ if(start + size > nums.size()) break; int sizesum = 0; for(int i = 0; i < size; i++){ sizesum += nums[start + i]; } if(sizesum > sum) sum = sizesum; } } return sum; } };

Optimization from Brute force

when get sum of subarray starts with the same num, we can avoid repetitive calculation by using subarray sum of smaller size

So we can start from each num and get all subarray sum started with it

passed test

Time: O(n*n)

Space: O(1)

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

class Solution { public: /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ int maxSubArray(vector<int> nums) { // write your code here int ans = INT_MIN; for(int start = 0; start < nums.size(); start++){ int sum = 0; for(int i = start; i < nums.size(); i++){ sum += nums[i]; ans = max(sum, ans); } } return ans; } };

Divide and Conquer:

Time: O(nlogn)

space: O(logn) -- stack depth

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 30

class Solution { public: /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ int maxSubArray(vector<int> nums) { if(nums.size() == 0) return 0; return helper(nums, 0, nums.size() - 1); } int helper(vector<int> &nums, int start, int end){ if(start == end) return nums[start]; int mid = (end + start) / 2; int left_max = helper(nums, start, mid); int right_max = helper(nums, mid + 1, end); int left_sum = INT_MIN, right_sum = INT_MIN; int sum = 0; for(int i = mid + 1; i <= end; i++){ sum += nums[i]; right_sum = max(right_sum, sum); } sum = 0; for(int i = mid; i >= start; i--){ sum += nums[i]; left_sum = max(left_sum, sum); } int ans = max(left_max, right_max); return max(ans, left_sum + right_sum); } };

Maybe can try backtracking method which is like get combinations

Kadane's Algorithm--one dimensional DP

Time: O(n)

Space: O(n)

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

class Solution { public: /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ int maxSubArray(vector<int> nums) { int sum = 0; int ans = INT_MIN; //incase no positive elements for(int i = 0; i < nums.size(); i++){ sum += nums[i]; ans = max(sum, ans); if(sum < 0) sum = 0; } return ans; } };