Kadane's Algorithm

It is the most asked question in Placements .So,if you are preparing for the placements then you should prepare this algorithm .

Kadane's Algorithm

 This algorithm is used to find the maximium subarray sum in an array . 
  These algorithm is asked many companies : Amazon,Ola,Hike,FactSet,Flipkart .


QUESTION
 
Given an array containing both negative and positive integers. Find the contiguous sub-array with maximum sum.
 
Print the maximum sum of the contiguous sub-array in a separate line for each test case.

INPUT

3

1 2 3

OUTPUT
6
Since maximum sum is(1+2+3) 6.


INPUT
4
-1 -2 -3 -4

OUTPUT
-1   

Since maximum subarray sum is -1

PROBLEM LINK:https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0



Program:

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

main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
   cin>>a[i];
}

int Max=a[0],sum=a[0];


for(int i=1;i<n;i++)
{


sum=max(a[i],sum+a[i]);


Max=max(Max,sum);
    }

cout<<Max<<"\n";



}


}




OUTPUT SCREEN