问题描述
显示错误的答案.有人可以告诉我我缺少哪个测试用例吗?
It's showing the wrong answer. Can anybody please tell me which test case I am missing ?
不相邻
给出N个正整数的数组arr [].任务是找到一个具有最大总和的子序列,以使子序列中的数组中不应该有相邻的元素.
Given an array arr[] of N positive integers. The task is to find a subsequence with maximum sum such that there should be no adjacent elements from the array in the subsequence.
输入:输入的第一行包含测试用例T的数量.对于每个测试用例,输入的第一行包含数组N的大小.下一行包含分隔的数组空间的N个元素.
Input:First line of input contains number of testcases T. For each testcase, first line of input contains size of array N. Next line contains N elements of the array space seperated.
输出:对于每个测试用例,请打印子序列的最大和.
Output:For each testcase, print the maximum sum of the subsequence.
约束:
1< = T< = 100
1< = N< = 10 ^ 6
1< = arr [i]< = 10 ^ 6
示例:
输入:
2
3
1 2 3
3
1 20 3
输出:
4
20
说明:
测试用例1:元素1和3组成一个具有最大和的子序列,并且该子序列中的任何元素在数组中都不相邻.
Testcase 1: Elements 1 and 3 form a subsequence with maximum sum and no elements in the subsequence are adjacent in the array.
测试用例2:数组中的元素20形成具有最大和的子序列.
Testcase 2: Element 20 from the array forms a subsequence with maximum sum.
我也尝试过使用以下测试用例
I tried using below test cases also
输入:
3
9
1 2 9 4 5 0 4 11 6
1
0
1
1
输出:
26
0
1
它工作正常,但在提交时给出了错误答案".我不知道它在谈论哪个测试用例
It worked fine but while submitting it was giving "wrong answer" I don't know for which test case it was talking about
这是我的解决方案:
#include<iostream>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int sum1,sum2,sum_even=0,sum_odd=0;
for(int i=0;i<n;i+=2)
sum_even+=arr[i];
for(int i=1;i<n;i+=2)
sum_odd+=arr[i];
if(n>=1)
sum1 = arr[0];
else
sum1 = -1;
if(n>=2)
sum2 = arr[1];
else
sum2 = -1;
int new_sum,i;
for(i=2; i<n; i+=2)
{
if((i+1)!=n && arr[i+1]>arr[i])
{
i++;
sum1+=arr[i];
}
else if(i+1==n)
{
sum1+=arr[i];
}
else
{
sum1+=arr[i];
}
}
for(i=3; i<n; i+=2)
{
if((i+1)!=n && arr[i+1]>arr[i])
{
i++;
sum2+=arr[i];
}
else if(i+1 ==n)
{
sum2+=arr[i];
}
else
{
sum2+=arr[i];
}
}
int sum = sum1>sum2 ? sum1 : sum2;
sum = sum>sum_odd ? sum : sum_odd;
sum = sum>sum_even ? sum : sum_even;
cout<<sum<<endl;
}
return 0;
}
推荐答案
问题是您似乎对任何解决方案的结构都做出了一些猜测.
您的代码非常复杂,很难手动找到有效的反例.
我随机生成了一个数组,并将您的结果与最佳数组进行比较.
我终于得到了这个反例:[14 18 8 19 22 1 20 23].您的代码给出的结果为64,而最佳总和等于67.
The issue is that you seem to made some guesses on the structure on any solution.
Your code is rather complex and it is difficult effectively to find a counter example by hand.
I made a random generation of arrays and compare your result with the optimal one.
I finally obtained this counter example : [14 18 8 19 22 1 20 23]. Your code gives a result of 64, while the optimum sum is equal to 67.
一个简单的最佳解决方案是迭代计算两个和,两个和都对应于当前索引 i
的最大值,不使用假定当前值 arr [i]
的第一个和( sum0
),假定当前值 sum1 )> arr [i] .
A simple optimum solution is to iteratively calculate two sums, both corresponding to a maximum up to the current index i
,the first sum (sum0
) assuming current value arr[i]
is not used, the second sum (sum1
) assuming the current value arr[i]
is used.
#include <iostream>
#include <vector>
#include <algorithm>
int max_sum (const std::vector<int>& arr) {
int sum0 = 0;
int sum1 = arr[0];
int n = arr.size();
for (int i = 1; i < n; ++i) {
int temp = sum0;
sum0 = std::max (sum0, sum1);
sum1 = temp + arr[i];
}
return std::max (sum0, sum1);
}
int main() {
int t;
std::cin >> t;
while(t--) {
int n;
std::cin >> n;
std::vector<int> arr(n);
for(int i = 0; i < n; i++)
std::cin >> arr[i];
int sum = max_sum (arr);
std::cout << sum << '\n';
}
}
这篇关于任务是找到一个具有最大总和的子序列,以使子序列中的数组中不应该有相邻元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!