Kadane's Algorithm - Contiguous Sub-Array With Maximum Sum

Contiguous sub array max sum

Max sum of contiguous array is a frequently asked and most widely asked question, it is mostly asked in placements and many interviews, so to impress HR  or to qualify placement rounds you need to use the best optimal solution.

Visual explanation 

Here we will see how  can we choose elements in order to get max sum

Here we can see that how we can choose elements from given elements of array.

Sometimes we can also add negative values as next value may be larger or continuous sum will be greater.

So in the above example we can see that we also included -2 in array sum as that gives the max sum. as 9.

Kadane's algorithm 

kadane's algorithm is a very benefitial algorithm which can be used similar to as of sliding window.

Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

Question Explanation 

Given an array arr of N integers. Find the contiguous sub-array with maximum sum.

Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A₁, A₂, ..., A_N denoting the elements of the array.

Output:
Print the maximum sum of the contiguous sub-array in a separate line for each test case.

Constraints:
1 ≤ T ≤ 110
1 ≤ N ≤ 10⁶
-10⁷ ≤ A[i] <= 10⁷

Example:
Input
2
5
1 2 3 -2 5
4
-1 -2 -3 -4
Output
9
-1

Explanation:
Testcase 1: Max subarray sum is 9 of elements (1, 2, 3, -2, 5) which is a contiguous subarray.

Solution (Optimal) using kadane's algorithm

#include<bits/stdc++.h>
using namespace std;
int main()
 {
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    int arr[n];
	    for(int i=0;i<n;i++)cin>>arr[i];
	    int max=-9999,max1=0;
	    for(int i=0;i<n;i++){
	        max1+=arr[i];
	        if(max1>max){
	            max=max1;
	        }
	        if(max1<0)
	        max1=0;
	    }
	    cout<<max<<endl;
	}
	return 0;
}