def maxProfit(self, prices: 'List[int]') -> 'int': profit = 0 for i, x in enumerate(prices): if i == len(prices) - 1: return profit if x < prices[i+1]: profit += prices[i+1] - x return profit

纪念一下我的第一次 “faster then 100%” （裸写的） “Runtime: 1 ms, faster than 100.00% of Java online submissions for Best Time to Buy and Sell Stock II.” public int maxProfit(int[] prices) { int profit = 0; for (int i = 0; i < prices.length - 1; i++) { if (prices[i] < prices[i + 1]) { profit += prices[i + 1 ] - prices[i]; } } return profit; }

DFS里每天有三种情况吧： 1. 买 2. 卖 3. 不动

贪心算法怎么才能证明是正确的呢

老师深度优先搜索怎么写啊，列出所有的情况

哪会知道第二天的股票是涨还是跌，这题目不合理

class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) return 0; int value = 0; int yestoday = prices[0]; for (int i = 0; i < prices.length; i++) { // 是否卖出？ int today = prices[i]; if (i > 0) { if (today > yestoday) { value += today; } yestoday = today; } // 是否买入？ if (i + 1 < prices.length) { int tomm = prices[i + 1]; if (tomm > today) { value -= today; } } } return value; } }

GO语言版本实现： func maxProfit(prices []int) int { var max int for i := 0; i < len(prices)-1; i++ { if prices[i+1] > prices[i] { max += prices[i+1] - prices[i] } } return max }

Go版本简单做法 func maxProfit(prices []int) int { profits := 0 for k, v := range prices { if k == 0 { continue } if v > prices[k-1] { // 后一天比前一天股价高，则卖出 profits = profits + v-prices[k-1] } } return profits }

写了一个超时的dfs static Map<Integer, Integer> cache = new HashMap<>(); public static int maxProfit3(int[] prices) { int res = 0; for (int i = prices.length - 2; i >= 0; i--) { res = Math.max(res, profit3(prices, i)); } return res; } private static int profit3(int[] prices, int begin) { int n = begin; int max = 0; if (cache.containsKey(begin)) { return cache.get(begin); } if (begin >= prices.length - 1) { return 0; } while (n != prices.length - 1) { int v = prices[n + 1] - prices[begin] + profit3(prices, n + 2); max = Math.max(v, max); n++; } int v = profit3(prices, begin + 1); if (max < v) max = v; cache.put(begin, max); return max; }