fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Kadane's Algorithm
  4. //
  5. //  Created by Himanshu on 17/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. using namespace std;
  10. const int N = 8;
  11.  
  12. void KadanesAlgorithm (int A[]) {
  13.     int maxSum = INT8_MIN, maxL = 0, maxR = 0, currMax = 0, l = 0, r = 0;
  14.  
  15.     for (int i=0; i<N; i++) {
  16.         currMax += A[i];
  17.         if (currMax > maxSum) {
  18.             maxSum =currMax;
  19.             r = i;
  20.             maxL = l;
  21.             maxR = r;
  22.         }
  23.         if (currMax < 0) {
  24.             currMax = 0;
  25.             l = i+1;
  26.             r = i+1;
  27.         }
  28.     }
  29.  
  30.     cout<<"Max contiguous subarray is A["<<maxL<<", "<<maxR<<"] with sum: "<<maxSum<<endl;
  31.  
  32. }
  33.  
  34. int main() {
  35.     int A[N] = {5, 3, -4, 6, -9, 8, 11, -20};
  36.     KadanesAlgorithm(A);
  37. }
  38.  
Success #stdin #stdout 0s 5644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max contiguous subarray is A[0, 6] with sum: 20
https://ideone.com/INZJQh
language:
C++ 4.3.2 (gcc-4.3.2)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!