一、问题描述：
如果一个人在知道了股票每天的股价以后，对该股票进行投资，问什么时候买入和卖出(注意这里有先后顺序）能取得最大的收益。其数学模型就是，给定一个整数数组，a[1],a[2],...,a[n]，每一个元素a[i]可以和它左边（a[i-1],a[i-2],...,a[0]）元素做差，求这个数组中最大的差值。
最初遇到这道题是在某度参加面试，当时只想到比较简单的方法。对于复杂度降低到O(n)的算法只是想到了大致思路但是没写出代码。
一、基本方法：
拿到这个题很容易想到，最直接，最基本的方法就是穷举。方法思路比较简单，但是复杂度极高O(n2)。
int max_sub(int *arr, int length){
int res = 0;
for(int i = 0; i < length-1; i++) {
for(int j = i; j < length; j++) {
int tmp = arr[j] - arr[i];
if(tmp > res) {
res = tmp;
}
}
}
return res;
}
二、降低复杂度的算法
如果要将复杂度降低到O(n)，一定要在一次循环得到结果。首先想到的是能不能用动态规划来解决。
如果记diff[i] 为第i个元素与其前面元素的差的最大值。那么可以得到方程
diff[1] = arr[1] - arr[0]; if diff[i-1] > 0 diff[i] = arr[i] - arr[i-1] + diff[i-1] else diff[i] = arr[i] - arr[i-1]
我们只用记录diff[i]的最大值即可得到结果。从上面的伪代码中可以看出来diff[i]只和diff[i-1]和arr[i],arr[i-1]有关。因此可以只用一个临时变量来保存diff[i-1]的值即可。
diff = arr[1] - arr[0] if diff > 0 diff = diff + arr[i] - arr[i-1] else diff = arr[i] - arr[i-1]
这样把空间复杂度降低到了O(1)。具体实现：
int max_sub2(int *arr, int len){
int res = 0;
int diff = 0;
for(int i = 1; i < len; i++) {
diff = diff >= 0 ? diff + arr[i] - arr[i-1] : arr[i] - arr[i-1];
if(diff > res) {
res = diff;
}
}
return res;
}
在遇到很多需要O(n)复杂度的场合，动态规划总是能够得到一个比较简单的解答。
>>>>>>>>>>>>>>>>>>>>
2013/6/16 21:58更新
根据在博客园里投递的同篇文章中@无忌小伙童鞋的评论：
正常正序遍历：
对于任意a[i]你肯定在遍历到a[i]时，你肯定能拿到a[i]之前的最小数（这个用一个变量保存），那么寻找最大差值就是a[i]与当前最小数的差值中的最大值（用一个变量存储，记为R）。
遍历结束后，R即为所求最大差值（对应的位置肯定知道了）。
对于任意a[i]你肯定在遍历到a[i]时，你肯定能拿到a[i]之前的最小数（这个用一个变量保存），那么寻找最大差值就是a[i]与当前最小数的差值中的最大值（用一个变量存储，记为R）。
遍历结束后，R即为所求最大差值（对应的位置肯定知道了）。
回想当时和x度面试官的讨论结果，整理一下思路比较简单的解法。
int max_sub(int *arr, int len) {
int min = arr[0];
int res = 0;
int tmp;
for(int i = 1; i < len; i++) {
if(arr[i] < min) {
min = arr[i];
}
tmp = arr[i] - min;
if(tmp > res) {
res = tmp;
}
}
return res;
}
欢迎各问大虾来讨论提供更简洁的算法