Smallest sum contiguous subarray / max difference of zeros and ones in a binary string
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
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}