What is the most intuitve explanation of Kadence algorithm to find maximum sum subarray?


#1

Iam new to the DP and trying to solve the maximum sum contiguous subarray.Can you give an intuitive explanation of Kadence algorithm?


#2

Kadane’s Algorithm:

Initialize:
max_so_far = 0
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
© if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

// C++ program to print largest contiguous array sum

#include
#include
using namespace std;

int maxSubArraySum(int a[], int size)
{
int max_so_far = INT_MIN, max_ending_here = 0;

for (int i = 0; i < size; i++)
{
    max_ending_here = max_ending_here + a[i];
    if (max_so_far < max_ending_here)
        max_so_far = max_ending_here;

    if (max_ending_here < 0)
        max_ending_here = 0;
}
return max_so_far;

}

/Driver program to test maxSubArraySum/
int main()
{
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
cout << "Maximum contiguous sum is " << max_sum;
return 0;
}
Source : wikipedia.com


#3

dint just copy paste frm wikipedia,your account can be compromised


#4

you have asked me to provide the links or sources thats what i have done .Matter along with source…


#5

Hi! To find out what I can do, say @gatestackbot display help.