给出 n n 个正整数 a 1 , a 2 , … , a n a 1 ​ ,a 2 ​ ,…,a n ​ ，要取出若干不相邻的数，求和的最大值。 输入格式 第一行输入一个数， n n。 第二行输入 n n 个以空格隔开的数。 输出格式 一个整数，表示和的最大值。1<=n<=10 4 1 < = a i < = 1 0 5 1<=a i ​ <=10 5用c++

<think>好的，我现在要解决这个问题：给定n个正整数，要求选出若干不相邻的数，使得它们的和最大。输入是n和这些数，输出最大值。这个问题看起来像是动态规划的经典题目，我需要仔细分析。 首先，我得理解问题。比如，假设数组是[1,2,3,4]，如果选2就不能选1或3。那么最大和应该是2+4=6？或者选1+3+4？哦不，不能相邻。所以选1+3+4的话，3和4是相邻的，不行。应该是选2+4或者1+3或者1+4，最大的应该是1+4=5？或者例子可能有误，或者我的理解有问题。可能需要再仔细看例子。 或者可能我举的例子不合适。比如数组是[1,2,3]，那么选1和3，和为4，或者选2，所以最大是4。所以在这种情况下，动态规划的方法应该能处理这种情况。 那怎么用动态规划呢？动态规划的关键是找到状态转移方程。对于这类问题，通常的处理方式是，对于每个位置i，我们有两种选择：选或者不选。 假设dp[i]表示前i个元素中满足条件的最大和。那么对于第i个元素，如果选的话，那么i-1不能选，所以dp[i] = dp[i-2] + a[i]。如果不选的话，dp[i] = dp[i-1]。所以dp[i]就是这两者的最大值。 或者，可能有的状态设计是每个状态有两个情况：选或不选当前元素。比如，设dp[i][0]表示前i个元素中，不选第i个时的最大和，dp[i][1]表示选第i个时的最大和。那么状态转移方程可能是： dp[i][0] = max(dp[i-1][0], dp[i-1][1]) → 因为当前不选的话，前一个可以选或者不选； dp[i][1] = dp[i-1][0] + a[i] → 因为当前选的话，前一个必须不选。 最后的结果就是max(dp[n][0], dp[n][1})。这可能更直观一些。 或者，另一种更节省空间的动态规划方式是只用两个变量，比如prev和curr。因为每次只需要前一个状态的信息。比如，对于每个位置i，我们可以维护两个变量：max_include_i（包含i的最大和）和max_exclude_i（不包含i的最大和）。或者，每一步维护前两个最大值。 不过对于n是1e4的情况，用O(n)的算法应该是可以的，因为时间上没有问题。空间的话，如果用数组的话，可能需要O(n)的空间，但也可以用滚动变量来优化到O(1)的空间。 比如，初始情况下： 如果数组只有一个元素，最大值就是a[0]。 如果有两个元素，max(a[0], a[1}). 对于第三个元素，有两种选择：选第三个的话，必须不选第二个，所以最大值是第一个元素的最大值加上第三个元素，或者不选第三个，那么最大值是前两个中的最大。所以更一般的情况，我们可以维护两个变量，prev_max和current_max。或者更具体地说，维护一个数组dp，其中dp[i]表示前i个元素的最大和。 比如，当i=0时，dp[0] = a[0] i=1时，dp[1] = max(a[0], a[1}) i>=2时，dp[i] = max(dp[i-1], dp[i-2]+a[i]) 这样，这个状态转移方程是否正确？ 举个例子： 数组是[3, 2, 7, 10]。按照这个方程： dp[0] =3 dp[1]=max(3,2)=3 dp[2]=max(3, 3+7=10 → 所以是10？ 或者原数组索引是否正确？要看数组是从0开始还是1开始。假设题目中的数组是0索引的话，那么i=2的时候是第三个元素，也就是7。这时候，选7的话，必须不选i=1的2，所以前i-2是dp[0] =3。所以总共有3+7=10。不选的话，dp[1]是3。所以max是10。这时候正确的结果应该是3+10=13？或者原数组的情况？ 哦，原数组是[3,2,7,10]。那么选3和7的话，是相邻的吗？3是第一个元素，2是第二个，7是第三个。所以3和7不相邻，可以选。这样总和是3+7+10？哦不行，因为7和10是相邻的。所以正确的选法应该是3+10=13，或者 2+10=12？或者7和10不能同时选。所以正确的最大值是13。那按照状态方程： dp[3] = max(dp[2], dp[1]+10) → dp[2]是max(dp[1], dp[0]+7)= max(3,3+7=10)=10。那么dp[3]是max(10, 3+10=13)=13。正确。所以状态方程是正确的。 那这说明动态规划的状态转移方程是正确的。所以我们可以用这个方程来计算。 那么对于实现来说，可以有两种方法：一种是使用一个数组dp，然后逐个计算；另一种是只用两个变量保存前两个状态，因为每个dp[i]只依赖于dp[i-1]和dp[i-2]。 例如，当处理到第i个元素时（假设数组索引从0开始），当前元素是a[i]。那么，我们可以用prev_prev表示dp[i-2]，prev表示dp[i-1]。然后当前dp[i] = max(prev, prev_prev + a[i]).然后，更新prev_prev为prev，prev为当前的值。这样，空间复杂度为O(1)。 那这样的话，当处理到每个元素的时候，只需要维护两个变量即可。这样的方式对于n=1e4来说没有问题，时间上是O(n)，空间也是常数。 那现在问题是如何处理数组的索引。假设输入的数组是arr，长度是n，索引从0到n-1。那么初始时： 如果n ==1，返回arr[0]。 否则： prev_prev = arr[0] prev = max(arr[0], arr[1]) 然后从i=2开始循环到n-1： current = max(prev, prev_prev + arr[i]) 然后更新prev_prev = prev，prev = current。 循环结束后，prev就是最大值。 但是当n=0时？不过题目中n>=1，所以无需处理。 测试例子： 例子1： 输入： n=3 数组是1 2 3 →最大是1+3=4？ 按照这个算法： i=0: prev_prev =1 i=1: prev = max(1,2)=2 i=2: current = max(2, 1+3=4) →4 所以最终结果是4，正确。 另一个例子，比如数组是[5,1,1,5]。那么正确解应该是5+5=10。 按照算法： i=0: prev_prev=5 i=1: prev = max(5,1)=5 i=2: current = max(5,5+1=6) →6 →此时prev_prev=5, prev=6 i=3: current = max(6,5+5=10) →10 →所以结果是10。正确。 所以这个算法是正确的。 那现在，如何用C++来实现？ 输入部分：首先读取n，然后读取n个整数到数组。然后处理。 需要注意的是，当n=1的时候，直接输出a[0]。 当n>=2的时候，初始化prev_prev和prev。 然后循环处理每个元素。 那具体代码的大致结构： #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i=0; i<n; ++i) { cin >> a[i]; } if (n == 0) { // 根据题目条件，n>=1，所以可以省略 cout << 0 << endl; return 0; } if (n ==1) { cout << a[0] << endl; return 0; } int prev_prev = a[0]; int prev = max(a[0], a[1]); for (int i=2; i<n; ++i) { int current = max(prev, prev_prev + a[i]); prev_prev = prev; prev = current; } cout << prev << endl; return 0; } 这样应该可以解决问题。但是需要考虑一些特殊情况吗？ 比如当n=2时，直接比较a[0]和a[1]，正确。 那对于n=4的情况，比如之前的例子： 数组是3,2,7,10： 初始化prev_prev=3，prev=max(3,2)=3. i=2时，a[i]=7: current = max(3,3+7=10) →10 →prev_prev=3 →prev=10. i=3时，a[i]=10: current = max(10,3+10=13) →13 →结果正确。 所以代码应该没问题。 那测试这样的代码是否可行？ 是的。那这个算法的时间复杂度是O(n)，空间是O(n)用于存储数组，或者可以边读边处理？例如，如果不需要保存整个数组的话，可以优化空间，但是题目中的输入方式是第二行输入n个数，所以必须读取整个数组。或者，可以边读边处理，在i>=2的时候才处理？ 比如，在读取数组的时候，前两个元素单独处理，后面的逐个处理？ 比如： int main() { int n; cin >> n; if (n ==1) { int x; cin >>x; cout <<x<<endl; return 0; } int a, b; cin >>a >>b; int prev_prev =a; int prev = max(a, b); for(int i=2; i<n; ++i) { int x; cin >>x; int current = max(prev, prev_prev +x); prev_prev = prev; prev = current; } cout << prev <<endl; return 0; } 这样，不需要存储整个数组，只需要读取每个元素。这在n很大的时候可以节省内存。例如，对于n=1e4来说，数组存储也没问题，因为1e4的int数组只占40KB左右。但边读边处理可能更节省空间。 不过，如果输入方式是第二行的n个数，那么在C++中可能需要一次性读取，因为输入可能被缓冲。例如，如果用户输入的是全部以空格隔开的数字，那么逐个读取是可以的。比如，在循环中，当i=0到n-1的时候，逐个读入。所以，当n>=2时，前两个数被读取，然后后面的逐个读取处理。 这可能更高效，尤其是当n很大时。所以，可以优化为不需要存储整个数组。 修改后的代码： #include <iostream> using namespace std; int main() { int n; cin >>n; if (n ==0) return 0; if (n ==1) { int x; cin >>x; cout <<x<<endl; return 0; } int a, b; cin >>a >>b; int prev_prev =a; int prev = max(a, b); for (int i=2; i<n; ++i) { int x; cin >>x; int current = max(prev, prev_prev +x); prev_prev = prev; prev = current; } cout << prev <<endl; return 0; } 这样，不管n的大小如何，都只需要保存前两个变量和当前的x。这应该可以正确运行吗？ 例如，当n=3时： 输入三个数，比如1 2 3。 处理： a=1，b=2 →prev_prev=1，prev=2. i=2循环进入，读取x=3. current = max(2,1+3=4) →4. 然后prev_prev=2，prev=4. 输出4，正确。 当n=4的情况： 输入3 2 7 10： a=3，b=2 →prev_prev=3，prev=3. i=2时读取7 →current = max(3,3+7=10) →prev_prev=3 →prev=10. i=3时读取10 →current = max(10,3+10=13) →输出13. 正确。 这样，这种处理方式是正确的。并且节省了存储整个数组的空间，适用于n非常大的情况。这可能更优。 那这样的代码是否能够处理所有情况？ 是的。那我认为这个解法是正确的。</think>要解决这个问题，我们需要找到一种方法，从给定的正整数数组中选出若干不相邻的数，使得它们的和最大。这个问题可以通过动态规划高效解决。 ### 方法思路 **动态规划**是解决此类问题的有效方法。我们定义两个变量来维护状态： - `prev_prev`：表示到前前个位置时的最大和。 - `prev`：表示到前一个位置时的最大和。 对于每个新元素，我们有两种选择： 1. 不选当前元素，此时最大和为前一个位置的最大和（`prev`）。 2. 选当前元素，此时最大和为前前个位置的最大和加上当前元素（`prev_prev + x`）。 我们取这两种选择的较大值作为当前的最大和，并更新状态变量。 ### 解决代码 ```cpp #include <iostream> #include <algorithm> using namespace std; int main() { int n; cin >> n; if (n == 1) { int x; cin >> x; cout << x << endl; return 0; } int a, b; cin >> a >> b; int prev_prev = a; int prev = max(a, b); for (int i = 2; i < n; ++i) { int x; cin >> x; int current = max(prev, prev_prev + x); prev_prev = prev; prev = current; } cout << prev << endl; return 0; } ``` ### 代码解释 1. **输入处理**：首先读取整数 `n`，如果 `n` 为1，直接读取并输出该数。 2. **初始化**：读取前两个数 `a` 和 `b`，并初始化 `prev_prev` 和 `prev`。 3. **循环处理**：从第三个元素开始逐个读取，计算当前的最大和，并更新状态变量。 4. **输出结果**：循环结束后，`prev` 即为所求的最大和。 这种方法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，非常高效，适用于较大的输入规模。