Best Time to Buy and Sell Stock

2020-05-22

121. Best Time to Buy and Sell Stock

原题：121. Best Time to Buy and Sell Stock

source code

// Runtime: 80 ms, faster than 33.60% of JavaScript online submissions for Best Time to Buy and Sell Stock.
// Memory Usage: 38.6 MB, less than 7.41% of JavaScript online submissions for Best Time to Buy and Sell Stock.
var maxProfit = function (prices) {
  let minBuy = prices.shift();
  let maxProfit = 0;
  for (let price of prices) {
    maxProfit = Math.max(maxProfit, price - minBuy);
    minBuy = Math.min(price, minBuy);
  }

  return maxProfit;
};

test cases:

test("test1", () => {
  expect(maxProfit([1, 2, 3, 4, 5])).toEqual(4);
});

test("test2", () => {
  expect(maxProfit([7, 6, 4, 3, 1])).toEqual(0);
});

test("test3", () => {
  expect(maxProfit([7, 1, 5, 3, 6, 4])).toEqual(5);
});

122. Best Time to Buy and Sell Stock II

原题：122. Best Time to Buy and Sell Stock II

这道题的思路是：因为能买卖无数次，只要能赚钱（价格比前一天高），就尽快卖出。能同一天进行买卖。

source code

// Runtime: 84 ms, faster than 27.73% of JavaScript online submissions for Best Time to Buy and Sell Stock II.
// Memory Usage: 37 MB, less than 23.81% of JavaScript online submissions for Best Time to Buy and Sell Stock II.
var maxProfit = function (prices) {
  let sum = 0;
  for (let i = 0, j = 1; j < prices.length; ) {
    if (prices[j] > prices[i]) {
      sum += prices[j] - prices[i];
    }
    i = j;
    j++;
  }

  return sum;
};

test cases

test("test1", () => {
  expect(maxProfit([7, 1, 5, 3, 6, 4])).toEqual(7);
});

test("test2", () => {
  expect(maxProfit([7, 6, 4, 3, 1])).toEqual(0);
});

test("test3", () => {
  expect(maxProfit([1, 2, 3, 4, 5])).toEqual(4);
});

123. Best Time to Buy and Sell Stock III

原题：123. Best Time to Buy and Sell Stock III

source code

// Runtime: 2064 ms, faster than 5.19% of JavaScript online submissions for Best Time to Buy and Sell Stock III.
// Memory Usage: 47.7 MB, less than 50.00% of JavaScript online submissions for Best Time to Buy and Sell Stock III.
var maxProfit = function (prices) {
  const helper = function (prices) {//helper实际上是121的代码
    let minBuy = prices.shift();
    let maxProfit = 0;
    for (let price of prices) {
      maxProfit = Math.max(maxProfit, price - minBuy);
      minBuy = Math.min(price, minBuy);
    }

    return maxProfit;
  };

  let maxProfit = 0;
  for (let i = 1; i <= prices.length; i++) {
    maxProfit = Math.max(
      maxProfit,
      helper(prices.slice(0, i)) + helper(prices.slice(i))
    );
  }

  return maxProfit;
};

test code

test("test1", () => {
  expect(maxProfit([3, 3, 5, 0, 0, 3, 1, 4])).toEqual(6);
});

test("test2", () => {
  expect(maxProfit([7, 6, 4, 3, 1])).toEqual(0);
});

test("test3", () => {
  expect(maxProfit([1, 2, 3, 4, 5])).toEqual(4);
});

test("test4", () => {
  expect(maxProfit([2, 1, 2, 0, 1])).toEqual(2);
});