DP --- Longest subarray whose sum <= K

Can still be solved using the recording sequence method, but also need another sequence to record the sum along the sequence.

C++ standard library:
partial_sum():
example: partial_sum (val, val+5, result);

partial_sum (val, val+5, result, std::multiplies<int>());

back_inserter: example: copy (bar.begin(),bar.end(),back_inserter(foo)); insert bar.begin() to bar.end() to the back of foo. If foo =[1 2 3] bar = [ 3 2 1], then foo = [1 2 3 3 2 1 ]

std::vector<int>::iterator low,up;
low=std::lower_bound (v.begin(), v.end(), 20); //first element smaller than 20
up= std::upper_bound (v.begin(), v.end(), 20); //first element bigger than 20 

The solution is based on following theory:
Let R[i] be partial sum, and T[i] = min(R[k]) for k=i to k=N-1, so T[i] is monotonically increasing.

Consider any index i. Let j be the largest index such that T[j]<=k+R[i]. We claim that longest subarray starting at i+1 that has a sum less than or equal to k must end at j, inclusive.

The solution is to find the longest alone all i.

Solution:

pair partialsum(const vector &A, const int k)
{
    vector parsum;
    partial_sum(A.cbegin(), A.cend(), back_inserter(parsum));

    vector minParSum(parsum);
    for(int i=minParSum.size()-2; i>=0; --i)
        minParSum[i] = min( minParSum[i], minParSum[i+1] );

    pair arridx(0, upper_bound(minParSum.cbegin(), minParSum.cend(), k) - minParSum.cbegin() - 1 );

    for(int i=0; i    {
        int idx = upper_bound(minParSum.cbegin(), minParSum.cend(), k+parsum[i]) - minParSum.cbegin() - 1;
        if (idx - i - 1 > arridx.second - arridx.first)
        arridx = {i+1, idx};
    }
    return arridx;
}