Smallest sum contiguous subarray / max difference of zeros and ones in a binary string

Easy

Problem

(1) Return the smallest sum of any contiguous subarray (Kadane's algorithm with min). (2) In a binary string, find the substring that maximises (number of 0s) − (number of 1s), or −1 if the string is all 1s.

Example 1

Input:  smallest sum [3, -4, 2, -3, -1, 7, -5]
Output: -6

[-4, 2, -3, -1].

Example 2

Input:  zeros − ones "11000010001"
Output: 6

Also asked as: Smallest sum contiguous subarray · Maximum difference of zeros and ones in binary string

Test cases

Case 1

Input:    [3,-4,2,-3,-1,7,-5]
Expected: -6

Case 2

Input:    [2,6,8,1,4]
Expected: 1

Case 3

Input:    [-1,-2]
Expected: -3

Case 4

Input:    [5]
Expected: 5

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Kadane, minimising (or on a transformed array)

Time O(n)Space O(1)

Smallest sum: run Kadane keeping the minimum running sum. Max (#0 − #1) over any substring: map 0→+1, 1→−1 and run standard maximum-subarray Kadane.

function smallestSubarraySum(a) {
let cur = a[0], best = a[0];
for (let i = 1; i < a.length; i++) {
cur = Math.min(a[i], cur + a[i]);
best = Math.min(best, cur);
}
return best;
}
function maxZeroMinusOne(bits) {
let cur = 0, best = 0, any = false;
for (const ch of bits) {
any = true;
cur = Math.max(ch === '0' ? 1 : -1, cur + (ch === '0' ? 1 : -1));
best = Math.max(best, cur);
}
return any ? Math.max(best, -1) : 0; // -1 if the string is all 1s
}