/*Write a program to take an integer array arr as input. The task is to find the maximum sum of any contiguous
subarray using Kadane's algorithm. Print the maximum sum as output. If all elements are negative, print the 
largest (least negative) element.*/
#include <stdio.h>
 
int main() {
    int n;
    scanf("%d", &n);
 
    int arr[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    int maxEnding = arr[0];
    int maxSoFar = arr[0];
 
    for (int i = 1; i < n; i++) {
        // Kadane's main step
        if (maxEnding + arr[i] > arr[i])
            maxEnding = maxEnding + arr[i];
        else
            maxEnding = arr[i];
 
        if (maxEnding > maxSoFar)
            maxSoFar = maxEnding;
    }
 
    printf("%d", maxSoFar);
    return 0;
}
 

LypXcml0ZSBhIHByb2dyYW0gdG8gdGFrZSBhbiBpbnRlZ2VyIGFycmF5IGFyciBhcyBpbnB1dC4gVGhlIHRhc2sgaXMgdG8gZmluZCB0aGUgbWF4aW11bSBzdW0gb2YgYW55IGNvbnRpZ3VvdXMKc3ViYXJyYXkgdXNpbmcgS2FkYW5lJ3MgYWxnb3JpdGhtLiBQcmludCB0aGUgbWF4aW11bSBzdW0gYXMgb3V0cHV0LiBJZiBhbGwgZWxlbWVudHMgYXJlIG5lZ2F0aXZlLCBwcmludCB0aGUgCmxhcmdlc3QgKGxlYXN0IG5lZ2F0aXZlKSBlbGVtZW50LiovCiNpbmNsdWRlIDxzdGRpby5oPgoKaW50IG1haW4oKSB7CiAgICBpbnQgbjsKICAgIHNjYW5mKCIlZCIsICZuKTsKCiAgICBpbnQgYXJyW25dOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgc2NhbmYoIiVkIiwgJmFycltpXSk7CgogICAgaW50IG1heEVuZGluZyA9IGFyclswXTsKICAgIGludCBtYXhTb0ZhciA9IGFyclswXTsKCiAgICBmb3IgKGludCBpID0gMTsgaSA8IG47IGkrKykgewogICAgICAgIC8vIEthZGFuZSdzIG1haW4gc3RlcAogICAgICAgIGlmIChtYXhFbmRpbmcgKyBhcnJbaV0gPiBhcnJbaV0pCiAgICAgICAgICAgIG1heEVuZGluZyA9IG1heEVuZGluZyArIGFycltpXTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIG1heEVuZGluZyA9IGFycltpXTsKCiAgICAgICAgaWYgKG1heEVuZGluZyA+IG1heFNvRmFyKQogICAgICAgICAgICBtYXhTb0ZhciA9IG1heEVuZGluZzsKICAgIH0KCiAgICBwcmludGYoIiVkIiwgbWF4U29GYXIpOwogICAgcmV0dXJuIDA7Cn0K

OQotMiAxIC0zIDQgLTEgMiAxIC01IDQK

9
-2 1 -3 4 -1 2 1 -5 4