53_ Maximum Subarray

Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

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.

Solution

Code

C++ - Iterative

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        
        int globalMaxSum = nums[0], currMaxSum = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            currMaxSum = max(currMaxSum + nums[i], nums[i]);
            globalMaxSum = max(globalMaxSum, currMaxSum);
        }
        return globalMaxSum;
    }
};

C++ - Recursive

class Solution {
public:
	int globalMaxSum;
	int maxSubArray(vector<int> &nums, int n) {
		if (n == 1) return nums[0];
		int currMaxSum = max(nums[n - 1], maxSubArray(nums, n - 1) + nums[n - 1]);
		globalMaxSum = max(globalMaxSum, currMaxSum);
		return currMaxSum;
	}
    int maxSubArray(vector<int> &nums) {
        globalMaxSum = nums[0];
		maxSubArray(nums, nums.size());
        return globalMaxSum;
    }
};

C++ - Brute-force

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
      int max_sum = nums[0];
      int n = nums.size();

      for (int i = 0; i < n; ++i) {
          for (int j = i; j < n; ++j) {
              int current_sum = 0;
              for (int k = i; k <= j; ++k) {
                  current_sum += nums[k];
              }
              if (current_sum > max_sum) {
                  max_sum = current_sum;
              }
          }
      }
    return max_sum;
    }
};
    

Reference
[1] https://leetcode.com/problems/maximum-subarray/solutions/1470547/c-easy-clean-solution-fastest-0ms-all-methods-follow-ups-detailed-explanation/