Kandane Algorithm - Alternative Approach IMP

PHOTO EMBED

Thu Jun 03 2021 19:02:16 GMT+0000 (UTC)

Saved by @Randumkeng

// in this we are storing current minimum from [0...r] and current sum [0...r] 
// there diff will give current maximum  
// imp thinking approach 


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

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

Search the subarray with the maximum/minimum sum

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