leetcode 121. Best Time to Buy and Sell Stock —– java

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.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5max. 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: 0In this case, no transaction is done, i.e. max profit = 0.

求最佳买入卖出时的收益。

暴力法，超时。

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

所以思考一下这道题的原理，其实就设定一个指针就好了

设定刚开始的数字是买入价格：

1、如果高于买入价格，那么就和result相比，取较大的。

2、如果是低于价格，那么更新买入价格。

public class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if( len < 2 )
            return 0;
        int result = 0;
        int buy = prices[0];
        for( int i = 1;i<len;i++){
            if( prices[i] > buy  )
            {
                result = Math.max(result,prices[i]-buy);
            }else
                buy = prices[i];
        }        return result;    }
}