AlaminSakib

Largest Sum Contiguous Subarray [BJIT]

Dec 18th, 2019
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.67 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int a[] = {-2, -3, -5, -1, -2, -1, -6, -3}, endd = 0, startt = 0, s = 0, maks_so_far = INT_MIN, maks_ending_here = 0;
  7.     for(int  i = 0; i < sizeof(a) / sizeof(a[0]); i++)
  8.     {
  9.         maks_ending_here += a[i];
  10.         if(maks_so_far < maks_ending_here)
  11.         {
  12.             maks_so_far = maks_ending_here;
  13.             startt = s;
  14.             endd = i;
  15.         }
  16.         if(maks_ending_here < 0)
  17.         {
  18.             maks_ending_here = 0;
  19.             s = i + 1;
  20.         }
  21.     }
  22.     cout << "start: " << startt << endl;
  23.     cout << "end:" << endd << endl;
  24.     cout << "sum:" << maks_so_far << endl;
  25. }
Add Comment
Please, Sign In to add comment