Maximum Subarray

#leetcode/53

Problem

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

Solution

Brute Force Algorithm

We sum all the elements between $i$ and $j$, and this for all the (contiguous) subarrays. Also, we keep track of the maximum sum found.

Solution in C++

int maxSubArray(vector<int>& nums){
    int maxSoFar = nums[0];
    int sum;
    for(int i = 0; i < nums.size(); ++i) {
        sum = 0;
        for(int j = i; j < nums.size(); ++j) {
            sum = sum + nums[j];
            maxSoFar = max(sum, maxSoFar);
        }
    }
    return maxSoFar;
}

• Time complexity: $O(N^2)$(where N is the size of the vector)
• Space complexity: $O(1)$

Optimal Algorithm

This algorithm is called "Kadane's Algorithm"
Graphic explanation:

Solution in C++

int maxSubArray(vector<int>& nums){
    int maxSoFar, maxHere;
    maxSoFar = maxHere = nums[0];
    for(int i = 1; i < nums.size(); ++i) {
        maxHere = max(maxHere + nums[i], nums[i]);
        maxSoFar = max(maxSoFar, maxHere);
    }
    return maxSoFar;
}

• Time complexity: $O(N)$(where N is the size of the vector)
• Space complexity: $O(1)$