description：

有n个水果 每个水果有个喜爱度ai 求连续最大长度水果喜爱值之和大于0

solution：

首先想到一个双指针 但是无法保证指针的移动就是对于答案有利的
1.维护一个后缀max前缀和 判断当前r指针往下走 是否对答案有利 如果sum[l] 也就是l的前缀和< last[r] 也就是r位置的后缀位置max前缀和 就可以保证l~r位置是 >0的 符合条件 继续伸展 反之的话 直接跳过

2.二分 二分的话其实和双指针的思路类似 我们维护一个前缀和sum 正向维护一个ai保存当前最小的前缀和 即ai = min(a[i - 1],sum) 设定二分上界为i+1 下界为0 二分去找和当前前缀和相近的位置 判断上下界和sum的关系 保证之间的差为正数 即符合题意 取最大值就好

3.排序 排序是最好理解的 结构体维护前缀和值和当前位置pos 根据贪心的思想肯定是值为第一优先选择 其次为pos降序排列 维护一个当前最小的pos值 只有当前pos值 < 最小pos值mi时 才有机会更新答案 特别要注意的是 排序的时候 x = 0 & pos = 0 的状态也要考虑进去 这也属于答案中的一种状态

code：

代码按照思路顺序给出

#include <bits/stdc++.h>

using namespace std;


const int N = 2e6 + 50,INF = 0x3f3f3f3f;

int sum[N],last[N];

int main(){
    ios::sync_with_stdio(0);

    int n;

    cin >> n;

    memset(last,-INF,sizeof(last));

    for(int i = 1;i <= n;i ++){
        int x;
        cin >> x;
        sum[i] = sum[i - 1] + x;
    }

    for(int i = n;i >= 1;i --){
        last[i] = max(last[i + 1],sum[i]);
    }

    int l = 0,r = 1,res = 0;

    for(;l < n;l ++,r ++){
        if(sum[l] >= last[r]){
            continue;
        }

        while(sum[l] < last[r] && r <= n){
            ++ r;
        }
        -- r;
        res = max(res,r - l);
    }

    cout << res << '\n';
    return 0;
}
#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x, a) memset(x, a, sizeof(x));
#define sca(a) scanf("%d", &a)
#define lowbit(x) x&(-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lson v << 1
#define rson v << 1 | 1
#define pii pair<int, int>

inline void read(int &x)
{
    x=0;
    int flag_read=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag_read=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    x *= flag_read;
}

void out(int x){
    if(x > 9){
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

const int N = 2e6 + 50;
#define LL long long

int a[N];

int main(){
    ios::sync_with_stdio(0);
    int n;

    cin >> n;

    int sum = 0;
    int res = 0;

    for(int i = 1;i <= n;i ++){
        int x;cin >> x;

        sum += x;
        a[i] = min(a[i - 1],sum);

        int l = 0,r = i + 1;

        while(l + 1 < r){
            int mid = l + r >> 1;
            if(a[mid] >= sum){
                l = mid;
            }else{
                r = mid;
            }
        }

        if(a[l] < sum){
            res = max(res,i - l);
        }else{
            res = max(res,i - r);
        }
    }

    cout << res << '\n';

    return 0;
}

排序

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x, a) memset(x, a, sizeof(x));
#define sca(a) scanf("%d", &a)
#define lowbit(x) x&(-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lson v << 1
#define rson v << 1 | 1
#define pii pair<int, int>

inline void read(int &x)
{
    x=0;
    int flag_read=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            flag_read=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    x *= flag_read;
}

void out(int x){
    if(x > 9){
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

const int N = 2e6 + 50;

struct node{
    int x;
    int pos;  
};

node a[N];

bool cmp(node a,node b){
    if(a.x != b.x){
        return a.x < b.x;
    }
    return a.pos > b.pos;
}

int main(){
    ios::sync_with_stdio(0);
    int n;

    cin >> n ;

    for(int i = 1;i <= n;i ++){
        int x;
        cin >> x;

        a[i].x = a[i - 1].x + x;
        a[i].pos = i;
    }

    sort(a ,a + 1 + n,cmp);

    int mi = 1 << 30,res = 0;

    for(int i = 0;i <= n;i ++){
        mi = min(mi,a[i].pos);
        if(mi < a[i].pos){
            res = max(res,a[i].pos - mi);
        }
    }

    cout << res << '\n';

    return 0;
}