Maximum Subarray Sum

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.

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

To solve this question click here:(https://leetcode.com/problems/maximum-subarray/)

Though it is a EASY LEVEL question but is really very important.

Brute force Approach:
Time Complexity: O(n^3)

C++ CODE:

#include<iostream>
#include<climits>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
      cin>>arr[i];
    int maxSum=INT_MIN;
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<n;j++)
        {
            int sum=0;
            for(int k=i;k<=j;k++)
                sum+=arr[k];
            maxSum=max(sum,maxSum);
        }
    }
    cout<<maxSum<<endl;
    return 0;
}

Enter fullscreen mode Exit fullscreen mode

This question can be solved in an optimized way by using Kadane Algorithm.
The simple idea of Kadane’s algorithm is to look for all positive contiguous segments of the array. And keep track of maximum sum contiguous segment among all positive segments

C++ CODE:

#include<iostream>
#include <climits>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    cin>>arr[i];

   int currSum=0;
   int maxSum=INT_MIN;
   for(int i=0;i<n;i++)
   {
       currSum+=arr[i];
       if(currSum<0)
           currSum=0;
       maxSum=max(maxSum,currSum);
   }
   cout<<maxSum<<endl;
    return 0;
}

Enter fullscreen mode Exit fullscreen mode

原文链接：Maximum Subarray Sum