Find Maximum Sum of Contiguous Subarray

Given an array of numbers, find the maximum sum of any contiguous subarray of the array.

Example:

Input:  nums[]={34,-50,42,14,-5,86}
Output: 137

Approach 1: Using Two For Loops

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the maximum
//subarray sum
int maxSubArray(vector<int> &nums)
{
    int n = nums.size();
    int max_sum = INT_MIN;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += nums[j];
            max_sum = max(sum, max_sum);
        }
    }
    return max_sum;
}
int main()
{
    vector<int> nums = {34, -50, 42, 14, -5, 86};
    cout << maxSubArray(nums);
    return 0;
}

//Time Complexity: O(n^2)
//Space Complexity: O(1)

Approach 2: Using Kadane's Algorithm

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the maximum
//subarray sum
int maxSubArray(vector<int> &nums)
{
    int max_sum = nums[0];
    int sum = nums[0];
    for (int i = 1; i < nums.size(); i++)
    {
        //if sum becomes zero or negative then
        //make it as 0
        if (sum <= 0)
            sum = 0;
        //add current element into sum
        sum += nums[i];

        //update the max_sum
        max_sum = max(sum, max_sum);
    }
    //return the max sum
    return max_sum;
}
int main()
{
    vector<int> nums = {34, -50, 42, 14, -5, 86};
    cout << maxSubArray(nums);
    return 0;
}

//Time Complexity: O(n)
//Space Complexity: O(1)