#include <bits/stdc++.h>
using namespace std;
 
int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0], max_ending_here = a[0];
   for(int i = 1; i < size; i++)
   {
     max_ending_here = max(max_ending_here + a[i],a[i]);
     max_so_far = max(max_so_far,max_ending_here);
    }
    return max_so_far;
} 
 
/*Driver program to test maxSubArraySum*/
int main()
{
   int a[] = {-2, -3, -17,-11, -2,-5, -3};
   int n = sizeof(a)/sizeof(a[0]);
   int max_sum = maxSubArraySum(a, n);
   printf("Maximum contiguous sum is %d\n", max_sum);
   getchar();
   return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWF4U3ViQXJyYXlTdW0oaW50IGFbXSwgaW50IHNpemUpCnsKICAgaW50IG1heF9zb19mYXIgPSBhWzBdLCBtYXhfZW5kaW5nX2hlcmUgPSBhWzBdOwogICBmb3IoaW50IGkgPSAxOyBpIDwgc2l6ZTsgaSsrKQogICB7CiAgICAgbWF4X2VuZGluZ19oZXJlID0gbWF4KG1heF9lbmRpbmdfaGVyZSArIGFbaV0sYVtpXSk7CiAgICAgbWF4X3NvX2ZhciA9IG1heChtYXhfc29fZmFyLG1heF9lbmRpbmdfaGVyZSk7CiAgICB9CiAgICByZXR1cm4gbWF4X3NvX2ZhcjsKfSAKIAovKkRyaXZlciBwcm9ncmFtIHRvIHRlc3QgbWF4U3ViQXJyYXlTdW0qLwppbnQgbWFpbigpCnsKICAgaW50IGFbXSA9IHstMiwgLTMsIC0xNywtMTEsIC0yLC01LCAtM307CiAgIGludCBuID0gc2l6ZW9mKGEpL3NpemVvZihhWzBdKTsKICAgaW50IG1heF9zdW0gPSBtYXhTdWJBcnJheVN1bShhLCBuKTsKICAgcHJpbnRmKCJNYXhpbXVtIGNvbnRpZ3VvdXMgc3VtIGlzICVkXG4iLCBtYXhfc3VtKTsKICAgZ2V0Y2hhcigpOwogICByZXR1cm4gMDsKfQ==