未排序数组中累加和小于或者等于k的最长子数组长度

题目描述

给定一个无序数组arr，其中元素可正、可负、可0。给定一个整数k，求arr所有的子数组中累加和小于或等于k的最长子数组长度

例如：arr = [3, -2, -4, 0, 6], k = -2. 相加和小于等于-2的最长子数组为{3, -2, -4, 0}，所以结果返回4

[要求]

时间复杂度为O(n)，空间复杂度为O(n)

输入描述:

第一行两个整数N, k。N表示数组长度，k的定义已在题目描述中给出
第二行N个整数表示数组内的数

输出描述:

输出一个整数表示答案

示例1

输入

5 -2
3 -2 -4 0 6

输出

4

#include<iostream>
#include<vector>

using namespace std;

int getLongestSumK(vector<int> arr, int k){
    if(arr.empty()) return 0;
    int n=arr.size();
    vector<int> minSum(n);
    vector<int> minSumEnd(n);
    minSum[n-1]=arr[n-1];
    minSumEnd[n-1]=n-1;
    for(int i=n-2;i>=0;i--){
        if(minSum[i+1]<0){
            minSum[i]=arr[i]+minSum[i+1];
            minSumEnd[i]=minSumEnd[i+1];
        }else{
            minSum[i]=arr[i];
            minSumEnd[i]=i;
        }
    }
    int end=0;
    int sum=0;
    int res=0;
    //i是窗口的最左位置，end是窗口最右位置的下一个位置
    for(int i=0;i<n;i++){
        while(end<n && sum+minSum[end] <=k){
            sum+=minSum[end];
            end=minSumEnd[end]+1;
        }
        res=max(res, end-i);
        if(end>i){
            sum-=arr[i];
        }else{
            end=i+1;
        }
    }
    return res;
}

int main(){
    int n, k;
    cin>>n>>k;
    vector<int> arr(n,0);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    cout<<getLongestSumK(arr, k)<<endl;
    return 0;
}