查找最大和正整数子数组

huangapple go评论72阅读模式
英文:

Finding Maximal-Sum Positive Integer Subarray

问题

给定一个由N个正整数组成的整数数组。你需要选择一个长度为K的子数组,子数组指的是数组的连续部分。你需要找到所有这样的子数组中具有最大和的子数组的和。

输入应该按照以下格式给出。第一行是N和K:数组的大小,要选择的子数组的大小。接下来一行是N个整数,Ai。
输出应该是答案,具有最大和的子数组的和。

限制条件
1 ≤ K ≤ N ≤ 1000,且 1 ≤ Ai ≤ 1000

我是这样解决的,但有2个测试出错了。我漏看了什么?

#include<iostream>
using namespace std;
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int n,k;
    cin>>n>>k;
    int a,s[n],sum=0,ans=0,ans1;
    for(int i=0; i<n; i++){
        cin>>a;
        sum+=a; 
        s[i]=sum;
    }
    if(k==n){
      cout<<sum<<endl;
      return 0;
    }
    for(int i=n-1; i>=0; i--){
       if(i-k>=0){
         ans1=s[i]-s[i-k];
       }
         ans=max(ans,ans1);
    }
    cout<<ans<<endl;
    return 0;}

https://algoleague.com/problem/max-subarray-2/detail

英文:

You are given an integer array consisting of N positive integers. You have to pick a subarray of length K. Subarray means a contiguous part of an array. You need to find the sum of the subarray with the maximal sum among all such subarrays.

Input should be given as follows. On the first line, N and K: the size of the array, the size of the subarray to choose. On the next line: N integers, Ai.
The output should be the answer, the sum of the subarray that has the maximal sum.

Constraints
1 ≤ K ≤ N ≤ 1000 and 1 ≤ Ai ≤ 1000

I solved it like this but 2 tests give errors. What have I overlooked?

#include<iostream>
using namespace std;
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int n,k;
    cin>>n>>k;
    int a,s[n],sum=0,ans=0,ans1;
    for(int i=0; i<n; i++){
        cin>>a;
        sum+=a; 
        s[i]=sum;
    }
    if(k==n){
      cout<<sum<<endl;
      return 0;
    }
    for(int i=n-1; i>=0; i--){
       if(i-k>=0){
         ans1=s[i]-s[i-k];
       }
         ans=max(ans,ans1);
    }
    cout<<ans<<endl;
    return 0;}

https://algoleague.com/problem/max-subarray-2/detail

答案1

得分: 4

以下是翻译好的部分:

"Without an example that reproduces the issue, it is extremely difficult to debug an algorithm. You probably feel stuck because I presume the only feedback you got was that your submission failed a certain number of tests. As you might guess, that is also frustrating for someone trying to answer your question.

This is not a criticism of you trying to get help with your question, but a general commentary on the types of questions that appear from some programming competition sites which appear not to give sufficient feedback to encourage good debugging techniques.

Given that is the situation, here is an idea. I read your code and I cannot find any issues. I also tested it with some sample data I generated and it passed all the tests. Below, you will find a different implementation that uses a sliding window. Maybe by comparing the two strategies, you can try to figure out if there are actually any differences."

int main(int argc, const char *argv[]) {
    int count, k;
    cin >> count >> k;

    int sum{};
    int arr[k];
    for (auto i = 0; i < k; ++i) {
        cin >> arr[i];
        sum += arr[i];
    }

    int max_sum{sum};
    for (auto i = k; i < count; ++i) {
        auto idx = i % k;
        sum -= arr[idx];
        cin >> arr[idx];
        sum += arr[idx];
        max_sum = std::max(max_sum, sum);
    }

    cout << max_sum << endl;
    return 0;
}
英文:

Without an example that reproduces the issue, it is extremely difficult to debug an algorithm. You probably feel stuck because I presume the only feedback you got was that your submission failed a certain number of tests. As you might guess, that is also frustrating for someone trying to answer your question.

This is not a criticism of you trying to get help with your question, but a general commentary on the types of questions that appear from some programming competition sites which appear not to give sufficient feedback to encourage good debugging techniques.

Given that is the situation, here is an idea. I read your code and I cannot find any issues. I also tested it with some sample data I generated and it passed all the tests. Below, you will find a different implementation that uses a sliding window. Maybe by comparing the two strategies, you can try to figure out if there are actually any differences.

int main(int argc, const char *argv[]) {
    int count, k;
    cin >> count >> k;

    int sum{};
    int arr[k];
    for (auto i = 0; i < k; ++i) {
        cin >> arr[i];
        sum += arr[i];
    }

    int max_sum{sum};
    for (auto i = k; i < count; ++i) {
        auto idx = i % k;
        sum -= arr[idx];
        cin >> arr[idx];
        sum += arr[idx];
        max_sum = std::max(max_sum, sum);
    }

    cout << max_sum << endl;
    return 0;
}

huangapple
  • 本文由 发表于 2023年5月25日 01:34:09
  • 转载请务必保留本文链接:https://go.coder-hub.com/76326093.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定