任务是找到一个具有最大总和的子序列，以使子序列中的数组中不应该有相邻元素

本文介绍了任务是找到一个具有最大总和的子序列，以使子序列中的数组中不应该有相邻元素的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

显示错误的答案.有人可以告诉我我缺少哪个测试用例吗?

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 )，假定当前值 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'; } }