英文:
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;}
答案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;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论