解题思路

• 本题要求在“最多持有一股、可多次交易（同一天可买或卖但不能同时持有多股）”的条件下，使收益最大。

• 相关算法：贪心 / 动态规划（两种说法等价）。

  • 贪心核心：只要今天价格比昨天高，就把这段上涨的差价计入收益，即累加所有相邻两天的正向差值 max(0, price[i] - price[i-1])。这样等价于在每一段上升区间“谷底买、峰顶卖”的效果。

  • 等价的 DP 表达（可作为思路背书）： 设 hold 为持有一股时的最大现金，cash 为不持有时的最大现金。 迭代转移：

    hold = max(hold, cash - price[i])     // 以当前价买入或继续持有
    cash = max(cash, hold + price[i])     // 以当前价卖出或继续空仓
    

    使用该 DP 也会得到与贪心相同的答案。

• 实现方法：遍历价格数组，从第二天起比较与前一天的差价，若为正则加入答案；最终输出总和。若不存在上升段则答案自然为 0。

复杂度分析

• 时间复杂度：O(n)，只需一次线性遍历。
• 空间复杂度：O(1)，仅用常数额外变量累计答案。

代码实现

Python

# 题面功能函数：计算最大收益（贪心：累加所有正向相邻差值）
def max_profit(prices):
    profit = 0
    # 遍历相邻两天，若上涨则把差价累加
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

# 主函数：ACM 风格输入输出
if __name__ == "__main__":
    import sys
    from ast import literal_eval

    # 读取 n（价格个数）
    n_line = sys.stdin.readline().strip()
    n = int(n_line)

    # 读取价格列表一行；优先尝试 literal_eval，其次再按空白分割
    s = sys.stdin.readline().strip()
    prices = []
    try:
        # 若形如 [7,1,5,4,6,4] 则可直接解析
        arr = literal_eval(s)
        if isinstance(arr, list):
            prices = [int(x) for x in arr]
        else:
            raise ValueError
    except Exception:
        # 兜底：把 [], , 替换为空白后 split
        cleaned = s.replace('[', ' ').replace(']', ' ').replace(',', ' ')
        prices = [int(x) for x in cleaned.split()]

    # 计算并输出答案（题目保证输入合法，不再校验长度）
    ans = max_profit(prices)
    print(ans)

Java

// 类名必须为 Main（ACM 风格）
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

    // 题面功能函数：计算最大收益（贪心法）
    // 使用 long 以避免极端情况下的整型溢出
    static long maxProfit(int[] prices) {
        long profit = 0L;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += (long) (prices[i] - prices[i - 1]);
            }
        }
        return profit;
    }

    // 主函数：读取输入并输出结果
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 读取 n（价格个数）
        int n = Integer.parseInt(br.readLine().trim());

        // 读取价格列表一行；优先“替换字符 + 输入流”方式解析
        String line = br.readLine();
        // 将可能出现的 '[', ']', ',' 替换为空格，便于按空白分割读取
        line = line.replace('[', ' ')
                   .replace(']', ' ')
                   .replace(',', ' ');
        StringTokenizer st = new StringTokenizer(line);

        int[] prices = new int[n];
        for (int i = 0; i < n && st.hasMoreTokens(); i++) {
            prices[i] = Integer.parseInt(st.nextToken());
        }
        // 题目默认输入合法，不做额外长度校验

        long ans = maxProfit(prices);
        System.out.println(ans);
    }
}

C++

// ACM 风格：主函数中处理输入输出；功能函数在外部
#include <bits/stdc++.h>
using namespace std;

// 题面功能函数：计算最大收益（贪心：累加相邻正差）
long long max_profit(const vector<long long>& prices) {
    long long profit = 0;
    for (size_t i = 1; i < prices.size(); ++i) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}

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

    int n;
    if (!(cin >> n)) return 0;   // 读取 n

    // 读取整行价格；先吃掉上一行残留，再取下一行
    string line;
    getline(cin, line);          // 读掉本行余下部分
    if (!getline(cin, line)) return 0;

    // “替换字符 + 输入流”：把 '[', ']', ',' 替换为空格
    for (char& c : line) {
        if (c == '[' || c == ']' || c == ',') c = ' ';
    }

    // 通过 stringstream 以空白分割解析数字
    stringstream ss(line);
    vector<long long> prices;
    long long x;
    while (ss >> x) prices.push_back(x);
    // 题目默认输入合法，不强制核对个数

    long long ans = max_profit(prices);
    cout << ans << '\n';
    return 0;
}

题目内容

给定一个正整数（表示股票价格列表的总个数）和一个非负整数列表（表示股票每天的价格）。用户初始不持有股票，要求每天仅能持有一份股票，且每天可以买入或卖出股票。计算通过买入卖出股票能获得的最大现金收益，若无法取得收益则返回 $0$ 。

输入描述

第一行输入一个整数 $n$ ，表示股票价格列表的总个数

第二行输入一个非负整数列表，表示股票每天的价格

输出描述

输出能获得的最大现金收益

样例1

输入

6
7 1 5 4 6 4

输出

6