2.1.3. Cumulative Sum

Sometimes, we also call cumulative sum as prefix sum, or left sum.

In C++, to cumulative sum, we can use partial_sum:

[cling]$ #include <sein.hpp>
[cling]$ vector<int> v={1,2,3,4};
[cling]$ partial_sum(v.begin(), v.end(), v.begin());
[cling]$ v
(std::vector<int> &) { 1, 3, 6, 10 }

2.1.3.1. Maximum Size Subarray Sum Equals k

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.

Example:
Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.
Code Block 2.1.4 Maximum Size Subarray Sum Equals k
 1int max_length_sum_k(vector<int>& nums, int k) {
 2  int csum = 0, r = 0;
 3  unordered_map<int, int> m;  // cumulative sum to index
 4  for (int i = 0; i < nums.size(); ++i) {
 5    csum += nums[i];
 6    if (csum == k)
 7      r = i + 1;
 8    else if (m.count(csum - k))
 9      r = max(r, i - m[csum - k]);
10    if (!m.count(csum)) m[csum] = i;
11  }
12  return r;
13}

2.1.3.2. Longest Subarray With Equal 0 and 1

Given a binary array, find the maximum length of a subarray with equal number of 0 and 1.

The O(N) solution to this problem is very clever. Replace all 0s with -1, and then use the Maximum Size Subarray Sum Equals k method (2sum) to solve, where k is 0.

Code Block 2.1.5 Max length of subarray with equal 0s and 1s
 1int max_length_equal01(vector<int>& n) {  // TC: O(N), SC: O(1)
 2  transform(n.begin(), n.end(), n.begin(), [](int i) { return i ? i : -1; });
 3  map<int, int> m;  // cumulative sum to index
 4  int csum = 0, r = 0;
 5  for (int i = 0; i < n.size(); ++i) {
 6    csum += n[i];
 7    if (csum == 0)
 8      r = i + 1;
 9    else if (m.count(csum))
10      r = max(r, i - m[csum]);
11    else
12      m[csum] = i;
13  }
14  return r;
15}

2.1.3.3. Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example:
Input: [23, 2, 6, 4, 7], k=6
Output: True
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42=6*7.

It is easy to prove that if the numbers a and b are divided by the number c, if the remainders are the same, then (a-b) must be able to divide c. According to this, the problem can be solved in O(N).

There are two troubles in this question: 1, the length of the subarray must be greater than or equal to 2; 2, if k is 0, there will be an edge case, and the logic will be different.

Code Block 2.1.6 subarray sum equals multiple of K
 1bool check_subarray_sum(vector<int>& n, int k) {
 2  if (n.size() < 2) return 0;
 3  if (k == 0) {
 4    for (int i = 0; i < n.size() - 1; ++i)
 5      if (n[i] == 0) return n[i + 1] == 0;
 6    return 0;
 7  }
 8  partial_sum(n.begin(), n.end(), n.begin());
 9  unordered_set<int> s = {n[0] % k};
10  for (int i = 1; i < n.size(); ++i) {
11    if (n[i] % k == 0 or s.count(n[i] % k)) return 1;
12    s.insert(n[i] % k);
13  }
14  return 0;
15}

2.1.3.4. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Code Block 2.1.7 Max sum subarray
1int max_sum_subarray(vector<int>& nums) {
2  int mx = *max_element(nums.begin(), nums.end());      // all negative case
3  partial_sum(nums.begin(), nums.end(), nums.begin());  // cum sum
4  int mi = nums[0], r = mi;
5  for (int i = 1; i < nums.size(); ++i)
6    r = max(r, nums[i] - mi), mi = min(mi, nums[i]);
7  return max(max(mx, r), *max_element(nums.begin(), nums.end()));
8}

👽 Find the index of the corresponding start and end.