Array DP
Description:
先说明题目意思，刚开始我看了很久也没搞明白，去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;
}
}
我对动态规划的理解还不够深刻，还需要多学习，多做这方面的题，加油！