给定一个整数数组nums，你需要选取其中的一些数字进行加法运算，使得得到的和最大，但相邻的数字不能同时被选取。请编写一个函数，返回可以获得的最大和，并输出选取的数字的索引。要求：请设计一种时间复杂度为O(n)的算法来解决此问题。

区块链毕设网qklbishe.com为您提供问题的解答

#include <iostream> #include <bits/stdc++.h> using namespace std;  int main() {     int x;      vector<int> nums;     while(true) {         cin >> x;         nums.push_back(x);         if(cin.peek() == 'n') break;     }     int n = nums.size();     vector<int> dp(n+1, 0);     vector<int> transition(n, 0);     dp[1] = nums[0];     transition[0] = 1;     for(int i = 2; i <= n; i++) {          // dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);         if(dp[i-1] > dp[i-2] + nums[i-1]) {transition[i-1] = 0; dp[i] = dp[i-1]; }         else {transition[i-1] = 1; dp[i] = dp[i-2] + nums[i-1]; }     }     vector<int> ans(n);     int k = 0;     for(int i = n - 1; i >= 0; ) {         if(transition[i]) {             ans[k++] = i;             i = i - 2;         } else {             i--;         }     }     for(k = k - 1; k >= 0; k--) {         cout << ans[k] << " ";     }     cout << endl;     cout << dp[n] << endl;  } // 64 位输出请用 printf("%lld")

编辑于 2024-04-15 20:16:38

以上就是关于问题给定一个整数数组nums，你需要选取其中的一些数字进行加法运算，使得得到的和最大，但相邻的数字不能同时被选取。请编写一个函数，返回可以获得的最大和，并输出选取的数字的索引。要求：请设计一种时间复杂度为O(n)的算法来解决此问题。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训