C++ Program to Implement Kadane’s Algorithm

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.

  1. #include <iostream>
  2. #include <climits>
  3. using namespace std;
  4.  
  5. #define MAX(X, Y) (X > Y) ? X : Y
  6. #define POS(X) (X > 0) ? X : 0
  7.  
  8. int maxSum = INT_MIN;
  9. int N;
  10. int kadane(int* row, int len)
  11. {
  12.     int x, sum, maxSum = INT_MIN;
  13.     for (sum = POS(row[0]), x = 0; x < N; ++x, sum = POS(sum + row[x]))
  14.         maxSum = MAX(sum, maxSum);
  15.     return maxSum;
  16. }
  17.  
  18. int main()
  19. {
  20.     cout << "Enter the array length: ";
  21.     cin >> N;
  22.     int arr[N];
  23.     cout << "Enter the array: ";
  24.     for (int i = 0; i < N; i++)
  25.     {
  26.         cin >> arr[i];
  27.     }
  28.     cout << "The Max Sum is: "<<kadane(arr, N) << endl;
  29.     return 0;
  30. }

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]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.