Question : You are given an array of integers.Your task is to find the contiguos subarry which has the largest sum and you need to return the sum of this subarray. (A subarray is a contiguous part of an array)

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

Brute Solution :

Example input array , a1={-2 , -3 , 4 , -1 , -2 , 1 , 5 , -3}
Three loops can be used here . The first loops runs from ( i=0 to n-1 ), where n is the size of the array.Second loops run from ; j=i to n-1 .Now you can see you have a subarray in between i and j .
Iterations :
1.i=0 and j=0
2.i=0 and j=1
3.i=0 and j=2
4.i=0 and j=3
.
.
z)i=0 and j=n-1
here you can see that there is subarrays from i to j , Now you can move your i one step forward , Now you will have subarrays from i=1 and j=1 to i=1 and j=n-1 and so on.
So in between i and j you will find all the subarrays.Now you can use the third loop from k= i to k= j to calculate the summation of that subarray and store the maximum one in a variable.

pseudo code :
for(i=0 to n-1)
for(j=i to n-1)
for(k=i to j)
{ sum+=ar[k]
maxsum=max(sum ,maxsum)
}

Time complexity : o(n^3)
Space complexity : o(n)

Optimal Solution :

The optimal solution is here kadane’s algorithm which comes with linear time complexity.
In this algorithm main idea is to look for all positive contiguous segments of the array.We will be using two variables here , one keeps the track of current sum and other keep the max_value we got till now .

maximum_in_array=INT_MIN
max_till_here=0
loop through the array :
a) max_till_here+=array[i]
b) if ( maximum_in_array < max_till_here) maximum_in_array=max_till_here
c) if ( max_till_here<0) max_till_here=0

Code :
C++
function to calcluate the maximum sum :
int maxSubArray(vector& nums) {

    int curr_sum=0;
    int max_sum=INT_MIN;

    for(int i=0;i<nums.size();i++)
    {
        curr_sum+=nums[i];
        if(curr_sum>max_sum)
        {
            max_sum=curr_sum;
        }
        if(curr_sum<0)
        {
            curr_sum=0;
        }


    }

    return max_sum;

}

Time complexity : O(n)
Space complexity : O(1)