解题思路

要求最大收益，我们需要找到最低的买入价格和在该买入价格之后的最高卖出价格。可以遍历一次数组：

  1. 用一个变量记录当前遍历过的最低价格
  2. 用另一个变量记录当前能获得的最大利润
  3. 对于每个价格，尝试更新最低价格，并计算当前价格卖出能获得的利润

代码

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

int maxProfit(vector<int>& prices) {
    if(prices.empty()) return 0;
    int minPrice = prices[0];
    int maxProfit = 0;
    
    for(int i = 1; i < prices.size(); i++) {
        maxProfit = max(maxProfit, prices[i] - minPrice);
        minPrice = min(minPrice, prices[i]);
    }
    return maxProfit;
}

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

import java.util.Scanner;

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

def max_profit(prices):
    if not prices:
        return 0
    min_price = prices[0]
    max_profit = 0
    
    for price in prices[1:]:
        max_profit = max(max_profit, price - min_price)
        min_price = min(min_price, price)
    return max_profit

n = int(input())
prices = list(map(int, input().split()))
print(max_profit(prices))

算法及复杂度

  • 算法：动态规划（一次遍历）
  • 时间复杂度：，其中 为数组长度
  • 空间复杂度：，只使用了常数个变量