Question:
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.
My code:
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2)
return 0;
int max = 0;
int i = 0;
while (i < prices.length) {
for (int j = i + 1; j < prices.length; j++) {
if (prices[j] <= prices[i]) {
i = j;
if (i == prices.length - 1)
return max;
else
break;
}
if (max < prices[j] - prices[i])
max = prices[j] - prices[i];
if (j == prices.length - 1)
return max;
}
}
return 0;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] prices = {2, 1};
System.out.println(test.maxProfit(prices));
}
}
My test result:
这次作业卡了一段时间，主要是题目的意思没有理解清楚。其实就是先要买，买了之后再卖。所以得在最低的时候买入，在最高的时候卖出，来赚取最多的钱。但是，又不是简单的找最大值最小值问题。简单的说，如果最小值出现在最大值之后，那么我买了最小值之后，无法卖出。因为数组是按时间排序的，最大值的那天已经过去了。
所以这道题目是简单的动态规划，以后我都会称之为， DP。
**
总结： 我设置两个指针。然后第二个指针开始往后遍历。如果碰到的值比第一个指针大，则不断刷新max值。当碰到的值比第一个指针小时，则第一个指针跳到第二个指针处。第二个指针开始从下一个值继续遍历。
以此循环。当然，比如输入时 [2,1]时，我这个算法会有一些问题。需要在排除一些情况，然后就对了。
写的还是不爽。
**
Anyway, Good luck, Richardo!
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0 || prices.length == 1)
return 0;
int[] max = new int[prices.length];
max[0] = 0;
int min = prices[0];
for (int i = 1; i < prices.length; i++) {
max[i] = Math.max(max[i - 1], prices[i] - min);
min = Math.min(min, prices[i]);
}
return max[max.length - 1];
}
}
** 没想到 **
----- 09/23/2015 23:25
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1)
return 0;
int buy = prices[0];
int max = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] < buy) {
buy = prices[i];
}
else {
max = Math.max(max, prices[i] - buy);
}
}
return max;
}
}
思路比较清晰。
感觉刷题这么久，进步还是有的。
Anyway, Good luck, Richardo!
