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.
advertisement
advertisement
Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.
If you find any mistake above, kindly email to [email protected]Related Posts:
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check C++ Books
- Check Computer Science Books
- Check Programming Books