Best Time to Buy and Sell Stock

Description

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Tags: Array, Dynamic Programmin

思路

题意是给出一个数组代表每天的股票金额，让你在最多买卖一次的情况下算出最大的收益额，最简单的就是模拟即可，每次记录当前值减去最小值的差值，与上一次的进行比较然后更新最大值即可。

Java:

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0, minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; ++i) {
            if (prices[i] < minPrice) minPrice = prices[i];
            int delta = prices[i] - minPrice;
            if (delta > max) max = delta;
        }
        return max;
    }
}

kotlin(204ms/100.00%):

class Solution {
    fun maxProfit(prices: IntArray): Int {
        if (prices.isEmpty()) return 0
        var ret = 0
        var min = prices[0]
        for (i in 1 until prices.size) {
            min = Math.min(min, prices[i])
            ret = Math.max(prices[i] - min, ret)
        }
        return ret
    }
}

var maxProfit = function(prices) {
  let finalProfit = 0
  for(var i = 0; i < prices.length; i++) {
      for(var j = 0; j < i; j++) {
          let profit = prices[i] - prices[j]
          if(profit > finalProfit) {
              finalProfit = profit
          }
      }
  }
  return finalProfit
};

结语

如果你同我们一样热爱数据结构、算法、LeetCode，可以关注我们 GitHub 上的 LeetCode 题解：LeetCode-Solution