Given an integer arrays, find a contiguous subarray which has the largest sum and length should be betweenk1andk2(include k1 and k2).
Return the largest sum, return 0 if there are fewer than k1 elements in the array.

Notice

Ensure that the result is an integer type.

Have you met this question in a real interview?

Yes

Example

Given the array[-2,2,-3,4,-1,2,1,-5,3]and k1 =2, k2 =4, the contiguous subarray[4,-1,2,1]has the largest sum =6.

class Solution {
public:
    /**
     * @param nums an array of integers
     * @param k1 an integer
     * @param k2 an integer
     * @return the largest sum
     */
    int maxSubarray5(vector<int>& nums, int k1, int k2) {
        // Write your code here
        if (nums.size() < k1) {
            return 0;
        }
        deque<int> q;
        int n = nums.size();
        vector<int> sum(n + 1, 0);
        int res = INT_MIN;
        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i - 1] + nums[i - 1];
            if (i >= k1) {
                inQueue(q, sum[i - k1]);
                res = max(res, sum[i] - q.front());
                if (i >= k2) {
                    outQueue(q, sum[i - k2]);
                }
            }
        }

        return res;
    }

    void inQueue(deque<int> &q, int val) {
        while (!q.empty() && val < q.back()) {
            q.pop_back();
        }
        q.push_back(val);
    }

    void outQueue(deque<int> &q, int val) {
        if (q.front() == val) {
            q.pop_front();
        }
    }
};