首页 > 试题广场 >

比特币最佳买卖时机

[编程题]比特币最佳买卖时机

热度指数：11021 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

如果你最多只允许完成一笔交易（即买入和卖出一次），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入比特币前卖出。

输入描述:

正整数数组，为以空格分隔的n个正整数

输出描述:

最大利润

示例1

输入

7 1 5 3 6 4

输出

算法知识视频讲解

Python

ElonB

"""
设dp[i]为以i为卖出点的最大收益
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    a = list(map(int, input().strip().split()))
    t_min = a[0]
    dp = []
    for i in range(len(a)):
        t_min = min(t_min, a[i])
        dp.append(a[i] - t_min)
    print(max(dp))

发表于 2019-07-10 16:28:31 回复(0)

Java

LHC0512

解法一：暴力解法，时间复杂度为 O(n²)

import java.util.Scanner;

public class Main {

    /**
     * 运行时间：60ms
     *
     * 占用内存：10688k
     * */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split(" ");
        int[] record = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            record[i]=Integer.parseInt(s[i]);
        }
        int max=0;
        for (int i = 0; i < s.length-1; i++) {
            for (int j = i+1; j < s.length; j++) {
                max=Math.max(max,record[j]-record[i]);
            }
        }
        System.out.println(max);
    }
}

解法二

import java.util.Scanner;

public class Main {
    /**
     * 运行时间：60ms
     *
     * 占用内存：10624k
     * */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int min = scanner.nextInt();
        int profit=0;
        while (scanner.hasNext()){
            int i = scanner.nextInt();
            profit=Math.max(profit,i-min);
            min=Math.min(i,min);
        }
        System.out.println(profit);
    }
}

编辑于 2020-03-01 22:35:33 回复(1)

顺德菜徐坤

因为只能一次买卖，所以记录下之前遍历过的最低价格，以后遇到比最低价格高的价格就更新最大利益；如果遇到更低价格就更新最低价格，重复上面操作，保证每次遇到一个数都能与此前的最低价格作差就可以得到该价格能卖出的最大收益；

#include <iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<math.h>
//#include<

using namespace std;

int main()
{
    int min_price = -1;
    int num,max_profit = 0;
    while (cin>>num) {
        if(min_price == -1)
            min_price = num;
        else {
            if(min_price > num)
                min_price = num;
            else {
                max_profit=max(num - min_price,max_profit);
            }
        }
    }
    cout<<max_profit<<endl;

    return 0;
}

发表于 2019-08-23 17:24:02 回复(0)

FlushHip

招商银行信用卡中心2019秋招IT笔试(AI、开发、测试开发方向)第一批

https://blog.csdn.net/FlushHip/article/details/84137906

发表于 2018-11-19 12:49:33 回复(0)

gonBorn

import java.util.Scanner;
import java.util.ArrayList;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        ArrayList<Integer> coin=new ArrayList<>();
        while(in.hasNextInt()){
            coin.add(in.nextInt());
        }
        Integer[] co=new Integer[coin.size()];
        coin.toArray(co);
        int profit=0;
        for(int i=co.length-1;i>=0;i--)
            for(int j=0;j<i;j++){
                profit=Math.max((co[i]-co[j]),profit);
            }
        System.out.println(profit);
    }
}

发表于 2019-03-02 00:49:26 回复(1)

pein531

直接计算第 i 天买入股票，之后哪天出售得到的收益最高即可

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strPrice = br.readLine().trim().split(" ");
        int[] price = new int[strPrice.length];
        for(int i = 0; i < price.length; i++) price[i] = Integer.parseInt(strPrice[i]);
        int maxIncome = 0;
        for(int i = 0; i < price.length - 1; i++){
            for(int j = i + 1; j < price.length; j++)
                maxIncome = Math.max(maxIncome, price[j] - price[i]);
        }
        System.out.println(maxIncome);
    }
}

发表于 2021-04-09 10:42:44 回复(0)

亚洲舞王智海

lis=list(map(int,input().split(' ')))
maxm=l=0
r=len(lis)-1
while l!=r :
    if (lis[l] - lis[l + 1] > lis[r-1] - lis[r]) :
        l+=1
    else :
        r-=1
    maxm=max(maxm,lis[r]-lis[l])
print(maxm)

发表于 2019-12-26 14:30:23 回复(0)

C/C++

nbgao

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

int main(){
    int x, Min=INT_MAX, s=0;
    while(cin>>x){
        s = max(s, x-Min);
        Min = min(Min, x);
    }
    cout<<s<<endl;
    return 0;
}

发表于 2019-11-21 01:12:23 回复(0)

Python

我要上岸！！

arr = [int(n) for n in input().split()]
dp = [0]*len(arr)
for i in range(1, len(arr)):
    for j in range(i):
        dp[i] = max(dp[i], arr[i]-arr[j])
print(max(dp))

发表于 2019-09-11 19:45:40 回复(0)

lentolove

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution2_比特币最佳买卖时机 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = bf.readLine().split(" ");
        int minprice = Integer.MAX_VALUE, max_profit = 0;
        for (int i = 0; i < line1.length; i++) {
            int a = Integer.parseInt(line1[i]);
            if (minprice > a) {
                minprice = a;
            }else if (a - minprice > max_profit){
                max_profit = a - minprice;
            }
        }
        System.out.println(max_profit);
    }
}

发表于 2019-08-09 20:20:02 回复(0)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int>p;
    int a=0,res=0;
    while(cin>>a)
        p.push_back(a);
    for(int i=p.size()-1;i>0;i--)
    {
        for(int j=i-1;j>=0;j--)
        {
            if(p[i]-p[j]>res)
                res=p[i]-p[j];
        }
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-07-02 15:42:31 回复(0)

Java

你的offer对我打了烊

import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bf.readLine().split(" ");
        int[] arr = new int[str.length];
        for(int i = 0;i < str.length;i++){
            arr[i] = Integer.parseInt(str[i]);
        }
        int maxprofit = 0;
        for(int i = 0;i < arr.length;i++){
            for(int j = i+1;j < arr.length;j++){
                if(arr[i] >= arr[j]){
                    continue;
                }else{
                    if((arr[j] - arr[i]) > maxprofit){
                        maxprofit = arr[j] - arr[i];
                    }
                }
            }
        }
        System.out.println(maxprofit);
    }
}

暴力遍历它不香吗

发表于 2020-03-04 20:15:49 回复(0)

凝视深空


	#include<bits/stdc++.h>



	using namespace std;



	 



	intmain() {



	    intn, mi = INT_MAX, maxProfit = 0;



	    while(cin >> n) {



	        maxProfit = max(n - mi, maxProfit);



	        mi = min(n, mi);



	    }



	    cout << maxProfit;



	    return0;



	}

发表于 2018-11-20 22:20:20 回复(7)

谁的电脑

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int buy = scanner.nextInt(), profit = 0;
        while (scanner.hasNext()) {
            // 输入新的价格
            int price = scanner.nextInt();
            // 每次输入新的价格时，更新最大利润
            profit = Math.max(profit, price - buy);
            // 每次输入新的价格时，更新最低买入价
            buy = Math.min(buy, price);
        }
        System.out.println(profit);
    }
}

发表于 2019-07-02 15:40:46 回复(1)

Java

斯九

import java.util.Scanner;
/*
*    O(n)的做法
*    对于第i个位置上的元素，我们只需要知道区间[0, i - 1]最小值，就可以得出第二个数的位置为i的最大差值有序偶，枚举i就可以得出答案；而区间[0, i - 1]最小值可以预处理出来。
*/
public class Main {
   public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int min = scanner.nextInt(), max = 0;
        int temp;
        while (scanner.hasNext()) {
            temp = scanner.nextInt();
            max = Math.max(max, temp - min);
            min = Math.min(min, temp);
        }
        System.out.println(max);
    }
}

java版

发表于 2019-03-03 08:17:55 回复(0)

A-GNAY

%卖出在买入之后，从0开始固定买入位置i后，从该位置往后的一位j进行卖出操作，直到最后一位。i进行到倒数第二位可停止，因为最后一天买入的话没时间卖出，没意义。将卖出与买入价格做差，放入列表，最后求列表中的最大值即可。注意，若差值小于0，则取0，不能为负数

P = list(map(int,input().split()))

b_list = []
b = 0
for i in range(len(P)-1):
for j in range(i+1,len(P)):
b = P[j]-P[i]
b_list.append(b)
print(max(0,max(b_list)))

发表于 2019-08-12 11:18:36 回复(0)

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var pre,x,ans int
    fmt.Scan(&pre)
    for{
        _,ok:=fmt.Scan(&x)
        if ok!=nil{
            break
        }
        if x>pre{
            if x-pre>ans{
                ans=x-pre
            }
        }else{
            pre=x
        }
    }
    fmt.Print(ans)
}

发表于 2023-03-22 19:39:02 回复(0)

如我一粒尘埃

import java.util.*;
import java.lang.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String in = sc.nextLine();
        String[] s = in.split(" ");
        int max = Integer.parseInt(s[0]);
        int min = Integer.parseInt(s[0]);
        int count = 0;
        for (int i = 1; i < s.length; i++) {
            int num = Integer.parseInt(s[i]);
            if (num < min) {
                min = num;
                continue;
            }
            if (num > max) {
                max = num;
                if (max - min > count) {
                    count = max - min;
                }
                continue;
            }
            if (num - min > count) {
                max = num;
                count = num - min;
            }
        }
        sc.close();
        System.out.println(count);
    }
}

发表于 2022-09-03 14:20:11 回复(0)

Python 3

牛客462162197号

a=list(map(int, input().split()))
max=0
for i in a:
    for j in a[a.index(i)+1:]:
        if max<j-i:
            max=j-i
print(max)

发表于 2021-10-18 21:11:50 回复(0)

牛客海清河晏

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner (System.in);
        List<Integer> arr=new ArrayList<Integer>();
        while(sc.hasNext()){ //判断是否结束
            int money = sc.nextInt();
            arr.add(money);
        }
        int len=arr.size();
        int[]prices=new int[len];
        for(int i=0;i<len;i++){
            prices[i]=arr.get(i);
        }
        int res=maxProfit(prices);
        System.out.println(res);
}
      public static int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

发表于 2021-10-14 19:27:23 回复(0)