解题思路

这是一个经典的动态规划问题：每个订单只能选或不选，但不能选择相邻订单。 设 dp[i] 表示考虑到第 i 个订单（下标从 0 开始）时能获得的最大收入，则：

• 不选第 i 个订单：收入为 dp[i-1]
• 选第 i 个订单：由于不能选相邻，所以收入为 dp[i-2] + a[i]

状态转移：

• dp[i] = max(dp[i-1], dp[i-2] + a[i]) 为简洁起见，用滚动变量代替数组：
• pre2 表示 dp[i-2]
• pre1 表示 dp[i-1] 逐个更新即可得到答案。

复杂度分析

• 时间复杂度：O(n)，遍历一次数组
• 空间复杂度：O(1)，只使用常数个变量

代码实现

Python

import sys

# 计算最大总金额（不能选相邻订单）
def max_income(a):
    # pre2 = dp[i-2], pre1 = dp[i-1]
    pre2, pre1 = 0, 0
    for x in a:
        # 当前 dp = max(不选当前, 选当前)
        cur = pre1 if pre1 > pre2 + x else pre2 + x
        pre2, pre1 = pre1, cur
    return pre1

def main():
    # ACM 输入：一行或多行整数
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    print(max_income(data))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {

    // 计算最大总金额（不能选相邻订单）
    public static long maxIncome(int[] a) {
        long pre2 = 0; // dp[i-2]
        long pre1 = 0; // dp[i-1]
        for (int x : a) {
            // 当前 dp = max(dp[i-1], dp[i-2] + x)
            long take = pre2 + x;   // 选当前订单
            long skip = pre1;       // 不选当前订单
            long cur = (skip > take) ? skip : take;
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        // 读到文件结束，适配不定长度输入
        while (sc.hasNextInt()) {
            list.add(sc.nextInt());
        }
        if (list.size() == 0) return;

        int[] a = new int[list.size()];
        for (int i = 0; i < list.size(); i++) a[i] = list.get(i);

        System.out.println(maxIncome(a));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 计算最大总金额（不能选相邻订单）
long long maxIncome(const vector<long long>& a) {
    long long pre2 = 0; // dp[i-2]
    long long pre1 = 0; // dp[i-1]
    for (long long x : a) {
        // 当前 dp = max(dp[i-1], dp[i-2] + x)
        long long take = pre2 + x; // 选当前订单
        long long skip = pre1;     // 不选当前订单
        long long cur = max(skip, take);
        pre2 = pre1;
        pre1 = cur;
    }
    return pre1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<long long> a;
    long long x;
    // ACM 输入：读到 EOF
    while (cin >> x) a.push_back(x);

    if (a.empty()) return 0;
    cout << maxIncome(a) << "\n";
    return 0;
}

题目内容

滴滴司机会收到预约订单，每个订单都可以选择接或不接。在每次约服务之间要有休息时间，因此他不能接受相邻的预约。给定一个预约请求序列，替滴滴司机找到最优的预约集合赚的总钱数最多，返回总的赚钱数。

输入描述

订单金额数组，$1<n<500$

输出描述

总的订单金额

样例1

输入

2 7 10 3 2

输出

14

说明

选择 $1$ 号预约、$3$ 号预约和 $5$ 号预约，总金额 $=2+10+2=14$

样例2

输入

1 2 4 1

输出

5

说明

选择 $1$ 号 $4$ 号，总金额 $=1+4=5$ 。