任务是找到一个具有最大总和的子序列，以使子序列中的数组中不应该有相邻元素 [英] The task is to find a subsequence with maximum sum such that there should be no adjacent elements from the array in the subsequence
问题描述
显示错误的答案.有人可以告诉我我缺少哪个测试用例吗?
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 )，假定当前值
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';
}
}
这篇关于任务是找到一个具有最大总和的子序列，以使子序列中的数组中不应该有相邻元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
