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














































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;
}


More Articles of srikant pani:

Name Views Likes
C++ tricks for competitive Part-1 572 2
C++ TRICKS FOR COMPETITIVE PART-5 385 2
C++ llrint() FUNCTION 316 1
C++ scalbln() 338 2
C++ nan() FUNCTION 434 1
C++ trunc() FUNCTION 425 1
C++ server client chat using socket programming 3778 2
C++ LAMBDAS 338 2
C++ TRICK AND TIPS PART-3 355 2
C++ TRICKS FOR COMPETITIVE PART-8 358 2
C++ TRICKS FOR COMPETITIVE PART-4 410 2
C++ expm1() 347 2
C++ fdim() 331 1
C++ TRICKS FOR COMPETITIVE PART-2 475 2
C++ abort() FUNCTION 465 1
C++ TRICK FOR COMPETITIVE PART-10 637 2
C++ remainder() FUNCTION 311 2
C++ TRICKS FOR COMPETITIVE PART-9 330 2
C++ TRICKS FOR COMPETITIVE PART-7 366 2
C++ frexp() FUNCTION 346 1
C++ Largest Sum Contiguous Subarray (Kadane%u2019s Algorithm) 554 2
C++ copysign() FUNCTION 306 1
C++ fma() FUNCTION 350 2
C++ TRICKS FOR COMPETITIVE PART-6 718 2
C++ hypot() FUNCTION 330 1

Comments

  • Khushi
    16-Nov-2020 09:56:45 AM
    Nice