 ### C++ Largest Sum Contiguous Subarray (Kadane%u2019s Algorithm)

INTERVIEWER:-Write an efficient program to find the sum of contiguous subarray within a one-dimensional array of numbers that has the largest sum.
STUDENT:- KADANE:-  DON'T WORRY.I AM HERE FOR YOU.
The simple idea of Kadane algorithm is to look for all positive contiguous segments of the array (SUM is used for this). And keep track of the maximum sum contiguous segment among all positive segments (MAX is used for this). Each time we get a positive-sum compare it with MAX and update MAX if it is greater than MAX.

EXAMPLE SUM IS INITIALIZE TO ZERO AND MAX=-2 SINCE SUM IS LESS THAN ZERO SO SUM=0 AND SUM=MAX SO MAX=-2 SINCE SUM IS LESS THAN ZERO SO SUM=0 AND SUM<MAX SO MAX=-2 SINCE SUM IS GREATER THAN ZERO SO SUM=0+5=5 AND SUM>MAX SO MAX=5 SINCE SUM IS GREATER THAN ZERO SO SUM=5-2=3 AND SUM<MAX SO MAX=5 SINCE SUM IS GREATER THAN ZERO SO SUM=3-1=2 AND SUM<MAX SO MAX=5 SINCE SUM IS GREATER THAN ZERO SO SUM=2+4=6 AND SUM>MAX SO MAX=6 SINCE SUM IS GREATER THAN ZERO SO SUM=6+1=7 AND SUM>MAX SO MAX=7 SINCE SUM IS GREATER THAN ZERO SO SUM=7-2=5 AND SUM<MAX SO MAX=7

MAX is the maximum sum of the subarray of the array.
TIME COMPLEXITY =O(N)               SPACE COMPLEXITY:-O(1)

CODE
`int` `maxSubArraySum(``int` `a[], ``int` `size) `
`{ `
`    ``int` `MAX = INT_MIN,SUM = 0; `
` `
`    ``for` `(``int` `i = 0; i < size; i++) `
`    ``{ `
`        ``SUM = SUM+ a[i]; `
`        ``if` `(MAX < SUM) `
`            ``MAX = SUM; `
` `
`        ``if` `(SUM < 0) `
`            ``SUM= 0; `
`    ``} `
`    ``return` `MAX; `
`} ` 