解题思路

这是一个求不相邻数字最大和的问题，可以通过动态规划来解决：

  1. 定义 表示前 个数中能选择的不相邻数字的最大和
  2. 对于第 个数，有两种选择：
    • 选择第 个数：
    • 不选择第 个数：
  3. 状态转移方程：
  4. 初始条件：

代码

#include <iostream>
#include <vector>
using namespace std;

long long maxSum(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    
    vector<long long> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
    }
    
    return dp[n-1];
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << maxSum(nums) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static long maxSum(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        long[] dp = new long[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        
        return dp[n-1];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(maxSum(nums));
    }
}

def maxSum(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
        
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[n-1]

n = int(input())
nums = list(map(int, input().split()))
print(maxSum(nums))

算法及复杂度

  • 算法：动态规划
  • 时间复杂度： - 只需要遍历一次数组
  • 空间复杂度： - 需要一个长度为 的 数组

这道题本质上是打家劫舍问题的变体。关键在于理解每个位置都有"选"和"不选"两种状态：

  1. 如果选择当前数字，那么前一个数字一定不能选，此时的和为
  2. 如果不选当前数字，那么最大和就是前 个数字能得到的最大和

由于数据范围较大（），所以在实现时需要使用 long long（C++）或 long（Java）类型来避免整数溢出。

注意：虽然题目保证输入的数字不超过 ，但是和可能会很大，所以需要使用长整型。