前言
中午在LintCode上看到一系列题目，看起来还蛮有意思的，于是先做了第一道。
题目
假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。
您在真实的面试中是否遇到过这个题？ Yes
样例
给出一个数组样例 [3,2,3,1,2], 返回 1
思路
暴力
很容易想到一个O(n2)的方法，求出数组中最大的prices[j] - prices[i]（j > i）:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null) {
return 0;
}
int l = prices.length;
if (l == 0) {
return 0;
}
int max = 0;
for (int i = 0; i < l; i++) {
for (int j = i + 1; j < l;j++) {
max = Math.max(max, prices[j] - prices[i]);
}
}
return max;
}
}
|
### 动态规划
显然上面的方法简单好理解但是不快。其实可以把价格数组中相邻两数之差作为一个新的数组sub，此时可以把问题转换为求最大的子数组和，复杂度就是O(n)了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null) {
return 0;
}
int l = prices.length;
if (l == 0) {
return 0;
}
int max = 0;
int temp = 0;
for (int i = 1; i < l; i++) {
int temps = prices[i] - prices[i - 1];
temp += temps;
max = Math.max(max, temp);
temp = temp<0?0:temp;
}
max = Math.max(max, temp);
return max;
}
}
|
