Kandane Algorithm

PHOTO EMBED

Thu Jun 03 2021 18:48:21 GMT+0000 (Coordinated Universal Time)

Saved by @Randumkeng

// one edge case when all elements are negative that time you sum can't be 0 so the answer would be 
// the minimum element in the array . 


int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, minus_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    if (sum > ans) {
        ans = sum;
        ans_l = minus_pos + 1;
        ans_r = r;
    }
    if (sum < 0) {
        sum = 0;
        minus_pos = r;
    }
}
content_copyCOPY

v

https://cp-algorithms.com/others/maximum_average_segment.html