fork download
copy 
  1. // Kadane Algorithm
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. int main() 
  7. {
  8.     // index    0   1  2  3  4
  9.     int b[5] = {5,-3,-5,15,5};
  10.     int T=0;
  11.     int n=5;
  12.     int prv=0;
  13.  
  14.     for(int i=0; i<n; i++)
  15.     {
  16.        // {Best answer till previous + current No , current No , so if both are negative consider the ans is zero }
  17.        // i=0
  18.         // current = max(0+5 , 5 ,0)
  19.         // prv = 5
  20.         // T = max(0,5) = 5
  21.  
  22.         //i=1
  23.         // current = max(5+(-3) , -3 , 0)
  24.         //prv = 2
  25.         //T = max(5,2) = 5
  26.  
  27.         //i=2
  28.         //current = max(2+(-5) , -5 , 0)  = max( -3 , -5 , 0) = 0 // becoz both -3 and -5 so the ans is consider as zero
  29.         //prv = 0
  30.         //T = max(5,0) = 5
  31.  
  32.         //i=3
  33.         //current = max(0+15 , 15 , 0 ) = max(15 , 15 , 0) = 15
  34.         //prv = 15  
  35.         //T = max( 5, 15) = 15
  36.  
  37.         //i=4
  38.         //current = max(15+5 , 5 , 0 ) = (20 , 5 , 0) = 20
  39.         //prv = 20
  40.         //T = max(15,20) = 20
  41.         int current = max({  prv+b[i]   ,   b[i]   ,  0  });
  42.         prv=current;
  43.         T=max(T,current);
  44.     }
  45.     cout<<"Max sum of subarray of the whole array: "<<T; // 20 will be the final answer
  46. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max sum of subarray of the whole array: 20
https://ideone.com/ZQYJ3h
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

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!