如何找到其和满足要求的子序列？

Question

我正在寻找一种方法来从序列中搜索最小后续大小，它的总和满足问题所需的最小总和。
示例（注意索引从0开始）：

arr[]={5, 1, 3, 5, 10, 7, 4, 9, 2, 8}  
sum = 15

所以答案应该是2，因为子序列的最小尺寸来自

a[3]-a[4].  
arr[]={1, 2, 3, 4, 5}  
sum = 11

所以答案应该是3，因为子序列的最小尺寸来自

a[2]-a[4].

我尝试使用贪心法，代码如下：

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector <int> sequence;

    int sequenceSize, sumAsked;
    cin>>sequenceSize>>sumAsked;
    
    int sum=0, count=sequenceSize, front=0, back=sequenceSize-1;

    for(int i=0; i<sequenceSize; i++){
        int j;
        cin>>j;
        sequence.push_back(j);
        sum+=j;
    }
    if(sum<sumAsked){
        cout<<0<<endl;
    }
    else{
        while(sum>sumAsked){
            if(sequence[front]>=sequence[back]){
                sum-=sequence[back];
                back--;
                count--;
            }
            else{
                sum-=sequence[front];
                front++;
                count--;
            }
        }
    cout<<count+1<<endl;
    }
}

代码似乎在两个测试用例上都有效，但在在线判断上却出错了。有没有更好的代码或方法供我使用？

Answer 1

我实际上得到了一个accepted法官的答复，看起来是这样的，

#include <bits/stdc++.h>
#define f first
#define s second

typedef long long int lli;
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int sequenceSize, sumAsked, sum=0;
    cin>>sequenceSize>>sumAsked;
    vector <int> sequence;
    for(int i=0; i<sequenceSize; i++){
        int j;
        cin>>j;
        sequence.push_back(j);
        sum+=j;
    }
    if(sum<sumAsked) cout<<0<<endl; //whether to check it's possible or not to get the answer,
    else{                           //otherwise it prints 0
        vector <int> note;
        int currentPos=0, currentSum=0, count=0;
        int temp=sequence[currentPos];
        for(int i=0; i<sequenceSize; i++){
            currentSum+=sequence[i];    //here we add the sum one by one from the sequence
            count++;
            while(!(currentSum-temp<sumAsked)){ //here we reduce the size of the 'window'
                currentSum-=temp;               //until it's just enough to hold the sum
                count--;
                cur++;
                temp=sequence[cur];
                note.push_back(count); //to take note all possible 'window' size
            }
        }
        for(int i=0; i<note.size(); i++){
            count=min(count, note[i]); //to search the best possible minimum answer
        }
        cout<<count<<endl;
    }
    return 0;
}

不过，我认为有可能不注意向量上的所有答案，但我认为这已经足够好了。

如何找到其和满足要求的子序列？

How to find a subsequence which it's sum satisfies requirements?

c++

sequence

greedy

sliding-window