【面试】求数组元素最大差值的问题

我会带着你远行 2022-01-20 23:57 191阅读 0赞

# 一、问题描述： #

如果一个人在知道了股票每天的股价以后，对该股票进行投资，问什么时候***买入和卖出***(***注意这里有先后顺序***）能取得最大的收益。其数学模型就是，给定一个整数数组，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)，一定要在一次循环得到结果。首先想到的是能不能用[***动态规划***][Link 1]来解决。

如果记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更新***

根据在博客园里投递的同篇文章中 [@无忌小伙][Link 2]童鞋的评论：

正常正序遍历：  
对于任意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;  
    }

*欢迎各问大虾来讨论提供更简洁的算法*

[Link 1]: http://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
[Link 2]: http://www.cnblogs.com/wanghaomiao/