算法 - 购买比特币的最佳时机

主题描述

给定一个正整数数组，它的第 i 个元素是比特币在第 i 天的价格。

如果您最多只能完成一笔交易（即买卖一次），请设计一种算法来计算您可以赚取的最大利润。

请注意比特币和股票性质一样吗，您不能在购买比特币之前出售。

输入描述

正整数数组比特币和股票性质一样吗，以空格分隔的 n 个正整数

输出描述

最大利润

分析：这是一个非常简单的动态问题，理解动态规划方法是一个非常经典的问题。只是改变了标题中的场景。从左到右遍历。当一个元素没有被遍历时，从当前元素中减去左边的最小值。

使用获得的结果与已获得的最小值进行比较。

动态规划方法：

适用情况：问题的解具有以下三个性质：最优子结构、无后效应、重叠子问题；

设计步骤：找出最优解的性质并描述其特征；递归定义最优值；自下而上计算最优解；根据构造最优值的过程得到最优解。

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String[] sArray = s.split(" ");
        int preMin = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int cur;
        for(int i = 0; i < sArray.length ; i++) {
            cur = Integer.valueOf(sArray[i]);
            max = Math.max(max, cur - preMin);
            preMin = Math.min(preMin, cur);
        }
        System.out.println(Math.max(max, 0));
     
    }
}