Kadane’s Algorithm in C++

This is a C++ Program to Implement Kadane Algorithm. Kadane algorithm is to used to obtain the maximum subarray sum from an array of integers.

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

```
#include <iostream>
```
```
#include <climits>
```
```
using namespace std;
```
```
 
```
```
#define MAX(X, Y) (X > Y) ? X : Y
```
```
#define POS(X) (X > 0) ? X : 0
```
```
 
```
```
int maxSum = INT_MIN;
```
```
int N;
```
```
int kadane(int* row, int len)
```
```
{
```
```
    int x, sum, maxSum = INT_MIN;
```

    for (sum = POS(row[0]), x = 0; x < N; ++x, sum = POS(sum + row[x]))

```
        maxSum = MAX(sum, maxSum);
```
```
    return maxSum;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    cout << "Enter the array length: ";
```
```
    cin >> N;
```
```
    int arr[N];
```
```
    cout << "Enter the array: ";
```
```
    for (int i = 0; i < N; i++)
```
```
    {
```
```
        cin >> arr[i];
```
```
    }
```

    cout << "The Max Sum is: "<<kadane(arr, N) << endl;

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

Output:

$ g++ Kadane.cpp
$ a.out
 
Enter the array length: 5
Enter the array: 1 -5 2 -1 3
The Max Sum is: 4
 
Enter the array length: 9
Enter the array: -2 1 -3 4 -1 2 1 -5 4
The Max Sum is: 6
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

« Prev - C++ Program to Implement the Hill Cipher

» Next - C++ Program to Find the Longest Increasing Subsequence

Related Posts:

Recommended Articles: