Array DP

Description:

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: 5

max. 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: 0

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

先说明题目意思，刚开始我看了很久也没搞明白，去Discuss上才看明白了。就是说，Input数组表示这段时间每天的货物价格，你以某个价格买入，之后再以那天的价格卖出，获取利益。例如：

Input: [7,1,5,3,6,4]

在价格为1时买入，价格为6时卖出，可获利润为5

Input: [7,6,4,3,1]

一直再降价，所以不买该货物，利润为0

Input: [2,4,1]

第一天买，第二天卖，可获利为2

Input: [3,2,6,5,0,3]

第二天买，第三天卖出，获利为4，比价格为0时买入，价格为3时卖出获利更多

my Solution:

public class Solution {

    public int maxProfit(int[] prices) {

        int n = prices.length;

        int profit = 0;

        if (n == 0) {

            return profit;

        }

        else {

            int min = prices[0];

            int max = prices[0];

            for (int i = 1; i < n; i++) {

                if (min >= prices[i]) {

                    min = prices[i];

                    max = min;

                }

                if (max <= prices[i]) {

                    max = prices[i];

                }

                profit = Math.max(profit, max-min);

            }

            return profit;

        }

    }

}

我的方法非常常规，这题最好的方法就是用动态规划的思想来解。

Best Solution:

public class Solution {

    public int maxProfit(int[] prices) {

        int maxCur = 0;

        int maxSoFar = 0;

        for (int i = 1; i < prices.length; i++) {

            maxCur = Math.max(0, maxCur + prices[i] - prices[i-1]);

            maxSoFar = Math.max(maxCur, maxSoFar);

        }

        return maxSoFar;

    }

}

我对动态规划的理解还不够深刻，还需要多学习，多做这方面的题，加油！