Approach #1 Brute Force [Accepted]
Intuition
Get the maximum sum subarray starting at each index. The maximum of these sums would be the ultimate maximum sum.
Algorithm
Traverse the vector using nested loops. The outer loop index would be the starting point of the subarray and the inner nested loop would be different end points for that subarray.
At each end point in the nested loop, we would adjust the max for the subarray starting at i
and ending at j
and at the end of loop, adjust the max if the array starting at index i have the maximum sum till now.
C++
public class Solution {
int maxSubArray(vector<int>& nums) {
int localmax = INT_MIN; //the maximum sum for the subarray starting at index i
int max = INT_MIN; // the overall maximum sum
for(int i=0; i<nums.size(); ++i) {
// Get max sum for the subarray starting at index i
int sum = 0;
for(int j=i; j<nums.size(); ++j) {
sum+=nums[j];
if(localmax < sum)
localmax = sum;
}
if(localmax > max)
max = localmax;
}
return max;
}
};
Complexity Analysis

Time complexity : $$O(n^2)$$.
We have 2 loops, one traversing the vector treating each element as the starting point of the subarray and the inner loop treating each index of the vector as the endpoint of that subarray.
For a given
i
, we traverse all the elements at index greater toi
of the vector.
Thus, the time complexity of this Algorithm is $$O(n^2)$$.
 Space complexity : $$O(1)$$ as we are not using any extra variable space.
Approach #2 Divide and Conquer Approach [Accepted]
Algorithm
The approach is to divide the problem into subproblems and get the maximum sum subarray.
We can divide the problem into max of following:
 The maximum sum of the left half of the vector,
 The maximum sum of the right half of the vector,
 The maximum sum of the subarray containing the middle element.
C++
class Solution {
private:
int maxSubArrayCrossed(vector<int>& nums, int l, int m, int h) {
// max sum from m>0 + max sum from m+1>h
int left_sum = INT_MIN;
int sum = INT_MIN;
for(int i=m; i>=l; i) {
sum += nums[i];
if(left_sum < sum) {
left_sum = sum;
}
}
int right_sum = INT_MIN;
sum = INT_MIN;
for(int i=m+1; i<=h; ++i) {
sum += nums[i];
if(right_sum < sum) {
right_sum = sum;
}
}
return left_sum + right_sum;
}
int maxSubArrayHelper(vector<int>& nums, int l, int h) {
if(l==h)
return nums[l];
int m = l+(h1)/2;
return max(
max(maxSubArrayHelper(nums, l, m), maxSubArrayHelper(nums, m+1, h)),
maxSubArrayCrossed(nums, l, m, h));
}
public:
int maxSubArray(vector<int>& nums) {
return maxSubArrayHelper(nums, 0, nums.size()1);
}
};
Complexity Analysis

Time complexity :
The time complexity can be expressed as the following recursive relation:
$$T(n) = 2T(n/2) + Θ(n)$$, as we are dividing the problem of sizen
into 2 subproblems each of sizen/2
and combining them in back in Θ(n).The above recursive relation is similar to the merge sort and has a worst case time complexity as $$Θ(nlogn)$$ using Master method.

Space complexity : $$O(n)$$ which is the recursion space.
Approach #3 Single traversal [Accepted]
Algorithm
The approach is to compute the maximum sum while doing the single traversal of the vector.
Keep track of the sum we have got sofar and if the current element is greater than the sum, update the sum and during the process, keep updating the max.
C++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max = INT_MIN, sum = 0;
for(const auto &n: nums) {
sum +=n;
if(sum < n)
sum = n;
if(max < sum)
max = sum;
}
return max;
}
};
Complexity Analysis

Time complexity : $$O(n)$$ as we are visiting each element once.

Space complexity : $$O(1)$$ as we are not using any additional variable space.