121.买卖股票的最佳时机

题目

假设你有一个数组，其中第 i 个元素是一支给定股票第 i 天的价格。

如果您只能完成最多一笔交易（即买入和卖出一股股票），则设计一个算法来找到最大的利润。

示例 1:

输入: [7, 1, 5, 3, 6, 4]
输出: 5

最大利润 = 6-1 = 5（不是 7-1 = 6, 因为卖出价格需要大于买入价格）

示例 2:

输入: [7, 6, 4, 3, 1]
输出: 0

在这种情况下, 没有交易完成, 即最大利润为 0。

思路

我们这样考虑：如果在第i天卖出股票，那么我们在那一天买入股票会使利润最大？答案是前i-1天中股票价格最低的那一天。一次遍历就可以解决这个问题了。用一个变量minPrice表示前i-1天的最低股票价格，用当前的股票价格减去minPrice就是在本天卖出的最低收益了，再根据是否超过记录的最大收益maxProfit来确认最大收益。

代码（含测试）

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] prices = new int[n];
        for(int i = 0; i < n; i++)
            prices[i] = scanner.nextInt();
        Solution soluton = new Solution();
        System.out.println(soluton.maxProfit(prices));
    }

    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0) return 0;
        int maxProfit = 0;
        int minPrice = prices[0];

        for(int i = 1; i < prices.length; i++) {
            maxProfit = Math.max(prices[i] - minPrice,maxProfit);

            if(prices[i] < minPrice) minPrice = prices[i];
        }

        return maxProfit;
    }
}