.. _cumsum:

Cumulative Sum
=============================================

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

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

.. code-block:: c++

    [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 }

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.


.. literalinclude:: code/cum_sum_test.cpp
    :language: c++
    :linenos:
    :lines: 28-40
    :emphasize-lines: 3, 9-10
    :caption: Maximum Size Subarray Sum Equals k
    :name: max_length_sum_k



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.

.. literalinclude:: code/cum_sum_test.cpp
    :language: c++
    :linenos:
    :lines: 11-25
    :emphasize-lines: 5-7, 9-10
    :caption: Max length of subarray with equal 0s and 1s
    :name: max_length_equal01


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.


.. literalinclude:: code/cum_sum_test.cpp
    :language: c++
    :linenos:
    :lines: 43-57
    :emphasize-lines: 4-6, 8, 11
    :caption: subarray sum equals multiple of K
    :name: check_subarray_sum


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.


.. literalinclude:: code/cum_sum_test.cpp
    :language: c++
    :linenos:
    :lines: 60-67
    :emphasize-lines: 2
    :caption: Max sum subarray
    :name: max_sum_subarray

|:alien:| Find the index of the corresponding start and end.

.. only: html

    https://leetcode.com/problems/maximum-subarray/