企业官网建设流程全解析

过年偷懒了两周现在又该好好学习了。今天白天浪费了太多时间，于是今晚选择刷两道又是之前算法课水过的题。看着当年的记录居然觉得也许或许当时可能是自己想出来的？！然而今天还是没想到做法QAQ

题目：

Say you have an array for which theith element is the price of a given stock on dayi.

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

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 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 Explanation: In this case, no transaction is done, i.e. max profit = 0.

题目的要求即是，给出一个数组，找出两数之差的最大值，其中较大值在较小值后面。这道题一看上去就觉得应该是动态规划来解，可是想了一下觉得好像划分不出来子问题，最后还是作弊看了以前的博客才醒悟——遍历整个数组，记录当前的最大profit和最小的price（quote以前写的：要先找出当前最小值并在循环的时候将现价与当前最小值相减得到的数字与当前最大利润进行比较）。醒悟以后很快写好了代码，又想了一下觉得不太像动态规划，看了discussion里面的解答才恍然大悟（嗯其实就是自己懒得去仔细推敲了，这种偷懒的毛病要改）：其实这个的子问题相当于max(profit[i - 1], prices[i] - min_price)，只是由于只有第一个元素需要存储，因此这个问题就简化得不太像动态规划了。代码如下，运行时间8ms，100%，空间9.6M，100%：

class Solution { public: int maxProfit(vector<int>& prices) { if (prices.size() == 0) { return 0; } int min_price = prices[0]; int max_profit = 0; for (int i = 1; i < prices.size(); i++) { if (prices[i] < min_price) { min_price = prices[i]; } if (prices[i] - min_price > max_profit) { max_profit = prices[i] - min_price; } } return max_profit; } };

然后呢，在翻discussion的时候突然看到有人提出来Max Subarray的Kadane算法，感觉这个名字有点熟悉啊，一看居然是春节前刷过的题，然而现在已经忘得一干二净了……这个帖子提出来说，我们目前是给定了每天的股票价格，而如果给出的是每天与前一天的差价，那么我们要怎么做呢？

懒惰的我当然是懒得想啦，继续看下去就发现居然这就变成了之前的Max Subarray那道题（LeetCode 53. Maximum Subarray），只需要找出连续的差价的最大值就是本题的答案了，这种联系真是妙极了！

2022.10.24 Java

嗯，多少年过去了，还是想不到思路。知道思路以后代码就好写了，然而还是忘了length == 0的情况。

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

2026.10.18

又不知道多少年过去了，依旧不会思路，但是写出的代码比上次简洁？算是有一点进步但不多。

class Solution { public int maxProfit(int[] prices) { int result = 0; int minPrice = prices[0]; for (int i = 1; i < prices.length; i++) { result = Math.max(result, prices[i] - minPrice); minPrice = Math.min(minPrice, prices[i]); } return result; } }