Kadane's Algorithm using Dynamic Programming

This is a C++ Program that Solves Kadane’s Algorithm using Dynamic Programming technique.

Problem Description

Maximum Subarray Problem
Given a sequence of n real numbers A(1) … A(n), determine a contiguous subsequence A(i) … A(j) for which the sum of elements in the subsequence is maximized.

Problem Solution

We will proceed in a linear fashion maintaining overall_max and current_max variables. If adding the current element to current_max results in overall maximum value, we will replace the value of overall_max variable. Otherwise, we will proceed furthere.

Expected Input and Output

Case-1:

 
A[]={2,4,6,8}
maximum contiguous subarry= {2, 4, 6, 8}
maximum contiguous subarray sum= 20

Case-2:

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

 
A[]={-2, 3, -7, 5, -9}
maximum contiguous subarry= {5}
maximum contiguous subarray sum= 5

Case-3:

 
A[]={3, -4, 7, -9, 8, 7}
maximum contiguous subarry= {8, 7}
maximum contiguous subarray sum= 15
 
A[]={3, -4, 9, -8, 8, 7}
maximum contiguous subarry= {9, -8, 8, 7}
maximum contiguous subarray sum= 16

Case-4:

Become Top Ranker in Data Structure I Now!

 
A[]={3, -4, 9, -8, 8, 7}
maximum contiguous subarry= {9, -8, 8, 7}
maximum contiguous subarray sum= 16

Program/Source Code for Brute force solution

Here is source code of the C++ Program to Solve Kadane’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
 
```
```
#include<iostream>
```
```
using namespace std;
```
```
 
```

//This function will check every contiguous subarray and return the sum of maximum subarray

```
int maxSubarraySum(int a[], int n)
```
```
{
```

    int overall_sum=0;  //overall maximum subarray sum

```
    int new_sum;
```
```
 
```
```
    for(int i=0;i<n;i++)
```
```
    {
```
```
 
```

        //find the maximum subarray sum of the subarray starting from a[i]

```
        new_sum=0;
```
```
        for(int j=i;j<n;j++)
```
```
        {
```
```
            new_sum+=a[j];
```
```
 
```
```
            if(new_sum>overall_sum)
```
```
            {
```
```
                overall_sum=new_sum;
```
```
            }
```
```
 
```
```
        }
```
```
    }
```
```
 
```
```
    return overall_sum;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,n;
```
```
 
```

    cout<<"Enter the number of elements in the array  ";

```
    cin>>n;
```
```
 
```
```
    int a[n];
```
```
 
```
```
    //read the vector
```

    cout<<"enter the elements in the array"<<endl;

```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>a[i];
```
```
    }
```
```
 
```

    //now,make a call to kadane function to calculate maximum subarray sum

    cout<<endl<<"The maximum subarray sum for the given array is "<<maxSubarraySum(a,n);

```
 
```
```
    return 0;
```
```
}
```

Program/Source Code for DP solution

Here is source code of the C++ Program to Solve Kadane’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
 
```
```
using namespace std;
```
```
 
```
```
int kadane(int a[], int n)
```
```
{
```

    int overall_sum=0;  //overall maximum subarray sum

    int new_sum=0;      //sum obtained by including the current element

```
 
```
```
    for(int i=0;i<n;i++)
```
```
    {
```

        //new_sum is the maximum value out of current element or the sum of current element

```
        //and the previous sum
```

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

```
 
```

        //if the calculated value of new_sum is greater than the overall sum,

        //it replaces the overall sum value

        overall_sum=max(overall_sum, new_sum);

```
    }
```
```
 
```
```
    return overall_sum;
```
```
 
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,n;
```
```
 
```

    cout<<"Enter the number of elements in the array  ";

```
    cin>>n;
```
```
 
```
```
    int a[n];
```
```
 
```
```
    //read the vector
```

    cout<<"enter the elements in the array"<<endl;

```
    for(i=0;i<n;i++)
```
```
    {
```
```
        cin>>a[i];
```
```
    }
```
```
 
```

    //now,make a call to kadane function to calculate maximum subarray sum

    cout<<endl<<"The maximum subarray sum for the given array is "<<kadane(a,n);

```
 
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the elements of the array. We pass this array to the function kadane as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ kadane.cpp
$ ./a.out
Enter the number of elements in the array 4
enter the elements in the array
2      
4
6
8
The maximum subarray sum for the given array is 20

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

» Next - Making Change Problem using Dynamic Programming

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Buy Computer Science Books
Buy Data Structure Books
Apply for Computer Science Internship
Practice Programming MCQs

Recommended Articles: