leetcode [#121]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Say you have an array for which the ith 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.

Example1:
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)

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

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

---

解决方案

public class Solution {
    public int maxProfit(int[] prices) {
        int N = prices.length;
        if(prices == null || N == 0) return 0;

        int max = 0;
        int temp = prices[0];
        for(int i = 1; i<N; i++){
            if(prices[i] > temp) {
                max = prices[i] - temp > max ? (prices[i] - temp) : max;
            } else {
                temp = prices[i];
            }
        }
        return max;
    }
}

---

注意事项

1. 只进行一次遍历，temp变量始终指向当前位置遍历过的元素中的最小的。
2. 如果当前元素大于temp,则考察两者之间的差是否比max变量中的值大，如果是，更新max值（max初始值为0，这样如果遍历完成时没有更大的，直接返回即可）。