秃头一半

其实二分查找可以用lower bound 代替

#include<iostream>
(720)#include<map>
#include<algorithm>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int inp[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&inp[i]);
    }
   int d[n + 1];
    d[0] = 0;
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += inp[i];
        d[i + 1] = max(sum, d[i]);
    }
    int count = 0, len = 0;
    sum = 0;
    for(int i = 0; i < n; i++){
        sum += inp[i];
        int tmp = sum - k;
        int* index = lower_bound(d,d+n+1,tmp);
        count = index  - d;
        len = max(len, i - count + 1);
    }
    cout<<len<<endl;
    return 0;
}

发表于 2020-05-03 10:31:17 回复(0)

Google-初级轮子工程师

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for(int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    vector<int> help(n+1);
    int res = -1;
    int sum = 0;
    help[0] = 0;
    for(int i = 0; i < n; ++i) {
        sum += arr[i];
        if(sum < help[i])
            help[i+1] = help[i];
        else
            help[i+1] = sum;
        // 二分法找sum-k
        int left = 0;
        int right = i;
        while(left <= right) {
            int mid = left + (right - left)/2;
            if(help[mid] >= sum - k) {
                res = max(res, i - mid + 1); //为什么+1，因为arr和help起始位置不同，换算
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
    }
    cout << res << endl;
    return 0;
}

发表于 2020-02-08 23:09:52 回复(0)

dragonlogin

#include <bits/stdc++.h>
using  namespace std;
struct A{
    int minSum; //以 i 开始，往右扩展，的最小和
    int minEnd; // 以 i 开始，往右扩展最小和的最右边界
};
int n, k;
int main() {
    cin >> n >> k;
    A *h = new A[n];
    int *a = new int[n];
    for (int i=0; i<n; ++i){
        cin >> i[a];
    }
    h[n-1].minSum = a[n-1];
    h[n-1].minEnd = n-1;

    for (int i=n-2; i>=0; --i) {
        if (h[i+1].minSum <= 0) {
            h[i].minSum = h[i+1].minSum + a[i];
            h[i].minEnd = h[i+1].minEnd;
        } else {
            h[i].minSum = a[i];
            h[i].minEnd = i;
        }
    }
    int ans = 0;
    for (int i=0; i<n; ++i) {
        if (h[i].minSum <= k) {
            int j = h[i].minEnd + 1;
            int sum = h[i].minSum;
            while (j < n) {
                sum += h[j].minSum;
                if (sum > k) {
                    break;
                } else {
                    j = h[j].minEnd + 1;
                }
            }
            ans = max(ans, j - i);
            if (j > n) {
               break;
            }
        }
    }
    cout << ans << endl;


    delete a;
    delete h;
    return 0;
}

发表于 2019-10-26 12:42:12 回复(0)

无心2019

#include<bits/stdc++.h>
using namespace std;
int getid(vector<int> & res, int x){
	int low = 0, hight = res.size() - 1, mid = 0, ans = -1;
	while (hight >= low){
		mid = (low + hight) / 2;
		if (res[mid] >= x){
			ans = mid;
			hight = mid - 1;
		}
		else
			low = mid + 1;
	}
	return ans;
}
int getlen(vector<int> & res, int x){
	vector<int>h(res.size() + 1, 0);
	int sum = 0;
	h[0] = sum;
	for (int i = 0; i < res.size(); i++){
		sum += res[i];
		h[i + 1] = max(h[i], sum);
	}
	sum = 0;
	int ans = 0, pre = 0, len = 0;
	for (int i = 0; i < res.size(); i++){
		sum += res[i];
		pre = getid(h, sum - x);
		len = pre == -1 ? 0 : i - pre + 1;
		ans = max(ans, len);
	}
	return ans;
}

int main()
{
    int n,x;
    cin>>n>>x;
    vector<int>res(n);
    for(int i=0;i<n;i++)
        cin>>res[i];
    cout<<getlen(res,x)<<endl;
    return 0;
}

发表于 2019-08-25 20:00:34 回复(3)

C/C++

Kai21

这套题比较新，也许因为比较简单（对萌新的我感觉还蛮难的），大佬们在讨论区都是直接贴代码就完事了。本题部分大佬贴的代码时间复杂度实际是O(nlog(n))，严格来说不符合题目要求，但也能通过，原因很简单，在for循环中套了二分查找，大家仔细看下就明白。

ok，进入主题，本题大致有两个思路：

1）借鉴前面的子数组求和思想，O(nlog(n))方案

在这套题中，一个潜在的假设是所求的子数组全是连续数组（觉得还是要提醒下大家），前面的数据问题均是这样。因此，借鉴这种思路，建立一个辅助的求和数组int sum[n]，在循环扫面的位置i处，寻找存在满足条件的最长子数组的核心是，找到sum-k所对应的位置。由于这道题大于等于k，因此，只要找到出现大于sum-k的最早位置j即可，那么j到i即为所满足条件的最大数组。

到此，问题转换为如何在长度为n的数组中，快速找到最早的大于等于sum-k的位置。在求sum[n]的过程中，需要进行一定处理，将其改造成单调非减数组，eg：

sum = {0 1 3 2 7 5} → sum = {0 1 3 3 7 7}

这样即可进行进行二分查找，时间复杂度O(nlog(n))。示例代码可见下面的@无心2019 po的。

2）O(n)方案

这个方案非常巧妙（我指实际代码实现的过程中，变量的更新控制很有意思）。相较于前一种方案的从前往后扫描生成求和数组sum[n]，这种方案使用了两个辅助数组：1）h[n]从后往前扫描计算对应位置i的最小累加和；2）ends[n]，用来记录当前位置所对应的累加和的结束位置；

首先，对数组arr[n]进行第一遍扫描，填满h[n]和ends[n]。

接着从左往右，根据arr[n]，ends[n]和arr[n]结算和寻找最长的子数组，原则很简单，相邻两端的和小于就继续，否则中断，进行长度比对，然后继续，直到end或i等于n。

Anyway, "talk is cheap, show me your code".

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    // special case
    if (n < 1)
        return 0;
    int arr[n];
    for (int i=0; i<n; i++){
        cin >> arr[i];
    }
    
    int h[n], ends[n];
    h[n-1] = arr[n-1];
    ends[n-1] = n-1;
    
    // 找到从i出发的最长的最小值子队列
    for(int i=n-2; i>-1; i--){
        if(h[i+1]<=0){
            h[i] = arr[i] + h[i+1];
            ends[i] = ends[i+1];
        }
        else{
            h[i] = arr[i];
            ends[i] = i;
        }
    }
    
    // 从前往后，依次寻找和比较从位置i出发，满足要求小于等于k的子数组并比较长度
    int len=0, end=0, sum=0;
    for(int i=0; i<n; i++){
        while(end<n && (sum+h[end]<=k)){
            sum += h[end];
            end = ends[end]+1;
        }
        len = max(len, end-i);         // 注意上面的循环退出条件，这里end实际上已经在符合条件的区间外了，所以无需再+1
        sum -= end > i ? arr[i]: 0;    // 同样注意上面的循环条件，如果end压根没动，sum值则未更新，不需要进行再次清零操作
        end = max(i+1, end);           // 同理，此时end恰好在边界外，无需+1
    }
    cout << len;
    return 0;
}
P.s 虽然在第二次循环中嵌套了while循环，但无需担心，因为在一次for循环的过程中，end总会前进while的步数，并且end不大于n，那么n即为上界；
P.s.s 务必注意end和sum的值更新，详细理由已在注释中写明；

发表于 2019-12-10 16:05:21 回复(0)

Java

pein531

这个O(N)时间复杂度的优化方案简直是毁***地级别的

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]);
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        // minSums[i]表示从i开始,往后数组的最小和;minSumEnds[i]表示这个最小和数组的边界
        int[] minSums = new int[n], minSumEnds = new int[n];
        minSums[n - 1] = arr[n - 1];
        minSumEnds[n - 1] = n - 1;
        for(int i = n - 2; i >= 0; i--){
            if(minSums[i + 1] < 0){
                // 右边是负贡献，直接累加上
                minSums[i] = arr[i] + minSums[i + 1];
                minSumEnds[i] = minSumEnds[i + 1];
            }else{
                minSums[i] = arr[i];
                minSumEnds[i] = i;
            }
        }
        int end = 0, sum = 0, maxLen = 0;
        for(int i = 0; i < n; i++){
            while(end < n && sum + minSums[end] <= k){
                // 满足累加和小于等于k就累加上
                sum += minSums[end];
                end = minSumEnds[end] + 1;
            }
            maxLen = Math.max(maxLen, end - i);
            if(end > i){
                sum -= arr[i];      // 窗口内还有救，把左边的元素弹出去试试
            }else{
                end = i + 1;        // 窗口内没救了，另起一个起点
            }
        }
        System.out.println(maxLen);
    }
}

发表于 2021-12-04 11:20:33 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int F(int *a, int n, int x){
    int l=0, r=n-1, m, p=-1;
    while(l<=r){
        m = (l+r)>>1;
        if(a[m]>=x){
            p = m;
            r = m-1;
        }else
            l = m+1;
    }
    return p;
}

int main(){
    int n, k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int b[n+1];
    memset(b, 0, sizeof(b));
    int s=0, Max=0, t=0, l=0;
    b[0] = s;
    for(int i=0;i<n;i++){
        s += a[i];
        b[i+1] = max(b[i], s);
    }
    s = 0;
    for(int i=0;i<n;i++){
        s += a[i];
        t = F(b, n+1, s-k);
        l = (t==-1?0:i-t+1);
        Max = max(Max, l);
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2020-02-09 00:01:23 回复(0)

C++

比那名居的桃子

简单在前缀和数组上二分。如果要求O(n)时间复杂度，把二分写法改成双指针即可。

#include<bits/stdc++.h>
using namespace std;
int sum[202020],a[202020];
int main(){
    int n,i,j,k,s=0,res=0,x;
    cin>>n>>k;
    for(i=1;i<=n;i++)cin>>a[i],sum[i]=s+=a[i];
    for(i=n-1;i>=1;i--)sum[i]=min(sum[i],sum[i+1]);
    int temp=0;
    for(i=0;i<=n;i++){
        temp+=a[i];
        res=max(res,int(upper_bound(sum+1,sum+n+1,temp+k)-sum-i-1));
    }
    cout<<res;
}

发表于 2022-04-19 14:43:17 回复(0)

acvv_khalil

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n, k;
int a[N], s[N];

int main() {
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];
    int ans = 0;
    for(int i=1, sum=0; i<=n; i++) {
        sum += a[i];
        int t = sum - k; // 找大于 t 的 最小index
        int it = lower_bound(s, s + i, t) - s;
        ans = max(ans, i - it);
        s[i] = max(sum, s[i-1]);
    }
    cout << ans << endl;
    return 0;
}

编辑于 2022-03-26 13:07:46 回复(0)

麦芒2021

利用sums数组表示前i项和，最前面加一个0；

求小于等于k的最长数组，就是求sum[i]-sum[j]<=k的最长数组，即sum[i]-k<=sum[j]，所所以需要找到大于等于sum[i]-k的位置；显然，只需要找到第一个满足大于等于sum[i]-k的位置，用辅助数组helper，helper[i]表示前i个和元素中的最大值；然后用二分法在helper中查找第一个大于等于sum[i]-k的位置，即可得到以i为结尾的满足和小于等于k的最大数组。

#include "bits/stdc++.h"

using namespace std;
int find(vector<int>&sums,int tmp)
{
    int n=sums.size();
    //if(tmp>sums[n-1]) return n;
    int l=0;int r=n;
    int mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(sums[mid]==tmp) {while(mid>0&&sums[mid]==sums[mid-1])mid--; return mid;}
        else if(sums[mid]<tmp){l=mid+1;}
        else if(sums[mid]>tmp){r=mid;}
    }
    return l;
}
int main()
{
    int len;cin>>len;
    int target;cin>>target;
    vector<int> sums(len+1,0);
    vector<int> helper(len+1,0);
    int sum=0;
    int tmp;
    int max_tmp=INT_MIN;
    for(int i=0;i<=len;i++)
    {
        cin>>tmp;
        sum+=tmp;
        sums[i]=sum;
        max_tmp=max(max_tmp,sums[i]);
        helper[i]=max_tmp;
    }
    int ret=0;
    for(int i=0;i<=len;i++)
    {
        tmp=sums[i]-target;
        int j=find(helper,tmp);
        if(j<=i) ret=max(ret,i-j);
    }
    cout<<ret;
    return 0;
}

发表于 2022-02-09 14:32:32 回复(0)

C++

五柳东坡

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int getLessIndex(vector<int>& arr, int num) {
    int low = 0;
    int high = arr.size() - 1;
    int mid = 0;
    int res = -1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (arr[mid] >= num) {
            res = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return res;
}

int maxLength(vector<int>& arr, int k ) {
    // 记录累加和
    vector<int> sumArr(arr.size(), 0);
    // 记录sumArr数组每个位置上的左侧最大值, 是有序的, 因此可以二分查找
    vector<int> helperArr(arr.size() + 1, 0);

    int sum = 0;
    helperArr[0] = sum;
    for (int i =0; i != arr.size(); i++) {
        sum += arr[i];
        sumArr[i] = sum;
        helperArr[i+1] = max(sum, helperArr[i]);
    }

    sum = 0;
    int res = 0;
    int pre = 0;
    int len = 0;
    for(int i = 0; i != sumArr.size(); i++) {
        sum = sumArr[i];
        // helperArr[x] >= sumArr[i] - k, x为满足此条件的最小下标
        // 即: sumArr[i] - helperArr[x] <= k
        // 然后 x ~ i 即为满足条件的最长子数组
        pre = getLessIndex(helperArr, sum - k);
        len = pre == -1 ? 0 : (i - pre + 1);
        res = max(res, len);
    }
    return res;
}

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

    cout << maxLength(arr, k) << endl;
}

发表于 2021-12-12 17:26:28 回复(0)

静静流淌

import java.util.*;

public class Main{
    public static void main(String [] args){
        Scanner input = new Scanner(System.in);
        int N,k;
        N = input.nextInt();
        k = input.nextInt();
        int [] arr = new int[N];
        int [] prefix = new int[N+1];
        int maxlen = 0;
        for(int i = 0;i < N;++i){
            arr[i] = input.nextInt();
            prefix[i+1] = prefix[i]+arr[i];
        }
        
        for(int i = 0;i < N;++i){
            int target = prefix[i+1]-k;   
            /*在prefix的[0,i]区间中找到第一个大于等于target的数的索引位置，没有则返回-1*/
            int tmp = find(prefix,target,0,i);
            if(tmp != -1){
                maxlen = Math.max(maxlen,i-tmp+1);
            }
            /*对前缀和进行特殊处理从而通过二分查找确定可能存在的最左边的边界*/
            prefix[i+1] = Math.max(prefix[i],prefix[i+1]);  
        }
        System.out.printf("%d\n",maxlen);
       
    }
    
    static int find(int[] prefix,int target,int left,int right){
        while(left < right){
            int mid = (right-left)/2+left;
            if(prefix[mid] >= target)
                right = mid;
            else{
                left = mid+1;
            }
        }
        return prefix[right] >= target ? right : -1;
    }
}

发表于 2021-04-24 21:51:02 回复(0)

Java

耐心and专注

借鉴已有思路：先获取每个位置的h[n]数组：从当前位置开始累加的最小值，end[n]数组：h[n]最小值得位置。然后从头开始循环数组：每个位置为左边界，也就是说，当前位置为最长序列的开始。

import java.util.*;
public class Main
{
public static int getMaxLen(int []arr,int target)
    {
        if(arr==null||arr.length==0)
        {
            return 0;
        }
        int maxLen=0,sum=0,endCur=0,n=arr.length;
        int []h=new int[n];
        int []end=new int[n];
        h[n-1]=arr[n-1];end[n-1]=n-1;//初始化数组 h[n]为从当前位置开始往后加的最小值 end[n]记录加到最小值的位置
        for(int i=n-2;i>=0;i--)//初始化数组
        {
            if(h[i+1]<=0)
            {
                h[i]=h[i+1]+arr[i];
                end[i]=end[i+1];
            }
            else {
                h[i]=arr[i];
                end[i]=i;
            }
        }
        //求返回值：从头开始遍历，每个位置为左边界
        for(int i=0;i<n;i++)
        {
            sum=h[i];endCur=i;
            while(endCur<n&&sum<=target)
            {
                endCur=end[endCur]+1;
                if(endCur<n)
                {
                    sum=sum+h[endCur];
                }

            }
            maxLen=Math.max(maxLen, endCur-i);

        }
        return maxLen;
    }
public static void main(String[]args)
{
Scanner in=new Scanner(System.in);
int N=in.nextInt(),k=in.nextInt();
int []arr=new int[N];
for(int i=0;i<N;i++)
{
arr[i]=in.nextInt();
}
System.out.println(getMaxLen(arr,k));
}
}

发表于 2020-11-17 00:28:21 回复(0)

C/C++

温柔岁月

class Solution {

public:

int maxSubArrayLen(vector<int>& nums, int k) {

unordered_map<int, int> m;

m.insert({0,-1});

// 0 和 -1

//有可能存在前缀和的情况

int sum = 0;

int res = 0;

for(int i = 0; i < nums.size(); i++){

sum += nums[i];

if (m.find(sum - k) != m.end())

res = max(res, i - m[sum - k]);

if (m.find(sum) == m.end())

m[sum] = i;

// 1 0

// 0 1

// 5 2

// 3 3

// 6 4

}

return res;

}

};

发表于 2020-10-20 20:41:09 回复(1)

木灬页

用二分做的，复杂度nlogn，这个复杂度过这道题没问题的，但我只过了60%用例，想不出原因。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        //答案在 0 - n 之间
        int left = 0;
        int right = n;
        int ans = 0;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(check(mid, arr, k)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.print(ans);
    }
    /**
        用连续 n个 能不能加起来小于 k
     */
    public static boolean check(int n, int[] arr, int k) {
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum += arr[i];
        }
        int left = 0;
        int right = n;
        while(sum > k && right < arr.length) {
            sum += arr[right++];
            sum -= arr[left++];
        }
        return sum <= k;
    }
}

发表于 2020-10-16 19:51:42 回复(0)

是兄弟就一起加班

C++滑动区间累积判定

这就是跟着书上写出来的代码，只优化了一个地方，就是区间右边界一旦到达数组边界，就直接跳出循环，因为从当前位置右侧出发的符合条件的数组不可能比当前位置到达末尾的子数组更长。

贴个代码，摸个鱼，骗点积分

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, k;
    cin>>N>>k;
    vector<int> nums(N);
    for(int i=0;i<N;++i)
        cin>>nums[i];
    vector<int> minSums(N), minSumEnds(N);
    minSums[N-1] = nums[N-1];
    minSumEnds[N-1] = N-1;
    for(int i=N-2;i>=0;--i){   // 生成minSums和minSumEnds
        if(minSums[i+1] <= 0){
            minSums[i] = nums[i] + minSums[i+1];
            minSumEnds[i] = minSumEnds[i+1];
        }
        else{
            minSums[i] = nums[i];
            minSumEnds[i] = i;
        }
    }
    
    int sum = 0, res = 0, right=0;
    for(int i=0;i<N && right<N;++i){  // 对每个初始位置寻找满足条件的最长子数组
        while(right<N && sum+minSums[right]<=k){
            sum += minSums[right];
            right = minSumEnds[right] + 1;
        }
        res = max(res, right-i);
        if(right > i)
            sum -= nums[i];
        else
            right = i+1;
    }
    cout<<res;
    return 0;
}

发表于 2020-07-18 20:59:41 回复(0)

AnnaSophia_Robb

O(N), start cur 不回退

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, k; scanf("%d%d", &n,&k);
    vector<int> arr(n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    vector<int> minSum(n,0);
    vector<int> minIndex(n,0);
    minSum[n-1] = arr[n-1];
    minIndex[n-1] = n-1;
    for(int i=n-2; i>=0; i--){
        if(minSum[i+1] <= 0){
            minSum[i] = arr[i] + minSum[i+1];
            minIndex[i] = minIndex[i+1];
        }else{
            minSum[i] = arr[i];
            minIndex[i] = i;
        }
    }
    int cur = 0, start = 0;;
    int sum = 0, len = 0;
    while(cur < n){
        sum += minSum[cur];
        if(sum <= k){
            len = max(len, minIndex[cur]-start+1);
            if(len >= (n-start)) break;
            cur = minIndex[cur] + 1;
        }else{
            while(sum > k){
                sum -= arr[start];
                start++;
            }
            len = max(len, minIndex[cur]-start+1);
            cur = minIndex[cur] + 1;
        }
    }
    cout << len;
    return 0;
}

发表于 2020-02-10 19:21:13 回复(0)

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int i=0;i<n;++i) cin>>v[i];
    vector<int>minSums(n);
    vector<int>minSumEnds(n);
    minSums[n-1] = v[n-1];
    minSumEnds[n-1] = n-1;
    for(int i=n-2;i!=-1;--i)
    {
        if(minSums[i+1]<0)
        {
            minSums[i] = v[i] + minSums[i+1];
            minSumEnds[i] = minSumEnds[i+1];
        }
        else
        {
            minSums[i] = v[i];
            minSumEnds[i] = i;
        }

    }
    int end = 0;
    int sum = 0;
    int res = 0;
    for(int i=0;i<n;++i)
    {
        while(end<v.size() && sum+minSums[end]<=k)
        {
            sum += minSums[end];
            end = minSumEnds[end] + 1;
        }
        res = max(res,end-i);
        if(end>i)
            sum-=v[i];
        else end = i+1;

    }
    cout<<res<<endl;
}

发表于 2020-02-09 15:32:00 回复(0)

字节快给我oc吧

import java.util.*; public class Main { public static void main(String[] args) {
        Scanner in = new Scanner(System.in);  int N = in.nextInt();  long k = in.nextLong();  int[] arr = new int[N];  for (int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }  int[] sums = new int[N];
        Map<Integer, Integer> map = new HashMap<>();
        sums[N-1] = arr[N-1];
        map.put(N-1, N-1);  for (int i = N-2; i >= 0; i--) {  if (sums[i+1] < 0) {
                sums[i] = arr[i] + sums[i+1];
                map.put(i, map.get(i+1));
            } else {
                sums[i] = arr[i];
                map.put(i, i);
            }
        }  int res = 0, sum = 0, end = 0;  for (int i = 0; i < N; i++) {  while (end < N && sum + sums[end] <= k) {
                sum += sums[end];
                end = map.get(end) + 1;
            }
            res = Math.max(res, end - i);
            sum -= end > i ? arr[i] : 0;
            end = Math.max(end, i+1);
        }
        System.out.println(res);
    }
}

发表于 2019-08-15 01:58:00 回复(0)

未排序数组中累加和小于或等于给定值的最长子数组长度

输入描述:

输出描述:

输入

输出

备注:

用二分做的，复杂度nlogn，这个复杂度过这道题没问题的，但我只过了60%用例，想不出原因。

C++滑动区间累积判定

问题信息

热门推荐

通过挑战的用户

相关试题