//
// main.cpp
// Kadane's Algorithm
//
// Created by Himanshu on 17/09/21.
//
#include <iostream>
using namespace std;
const int N = 8;
void KadanesAlgorithm (int A[]) {
int maxSum = INT8_MIN, maxL = 0, maxR = 0, currMax = 0, l = 0, r = 0;
for (int i=0; i<N; i++) {
currMax += A[i];
if (currMax > maxSum) {
maxSum =currMax;
r = i;
maxL = l;
maxR = r;
}
if (currMax < 0) {
currMax = 0;
l = i+1;
r = i+1;
}
}
cout<<"Max contiguous subarray is A["<<maxL<<", "<<maxR<<"] with sum: "<<maxSum<<endl;
}
int main() {
int A[N] = {5, 3, -4, 6, -9, 8, 11, -20};
KadanesAlgorithm(A);
}
Ly8KLy8gIG1haW4uY3BwCi8vICBLYWRhbmUncyBBbGdvcml0aG0KLy8KLy8gIENyZWF0ZWQgYnkgSGltYW5zaHUgb24gMTcvMDkvMjEuCi8vCgojaW5jbHVkZSA8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBOID0gODsKCnZvaWQgS2FkYW5lc0FsZ29yaXRobSAoaW50IEFbXSkgewogICAgaW50IG1heFN1bSA9IElOVDhfTUlOLCBtYXhMID0gMCwgbWF4UiA9IDAsIGN1cnJNYXggPSAwLCBsID0gMCwgciA9IDA7CiAgICAKICAgIGZvciAoaW50IGk9MDsgaTxOOyBpKyspIHsKICAgICAgICBjdXJyTWF4ICs9IEFbaV07CiAgICAgICAgaWYgKGN1cnJNYXggPiBtYXhTdW0pIHsKICAgICAgICAgICAgbWF4U3VtID1jdXJyTWF4OwogICAgICAgICAgICByID0gaTsKICAgICAgICAgICAgbWF4TCA9IGw7CiAgICAgICAgICAgIG1heFIgPSByOwogICAgICAgIH0KICAgICAgICBpZiAoY3Vyck1heCA8IDApIHsKICAgICAgICAgICAgY3Vyck1heCA9IDA7CiAgICAgICAgICAgIGwgPSBpKzE7CiAgICAgICAgICAgIHIgPSBpKzE7CiAgICAgICAgfQogICAgfQogICAgCiAgICBjb3V0PDwiTWF4IGNvbnRpZ3VvdXMgc3ViYXJyYXkgaXMgQVsiPDxtYXhMPDwiLCAiPDxtYXhSPDwiXSB3aXRoIHN1bTogIjw8bWF4U3VtPDxlbmRsOwogICAgCn0KIAppbnQgbWFpbigpIHsKICAgIGludCBBW05dID0gezUsIDMsIC00LCA2LCAtOSwgOCwgMTEsIC0yMH07CiAgICBLYWRhbmVzQWxnb3JpdGhtKEEpOwp9Cg==