} } }

    【口试】求数组元素最大差值的题目

    添加时间:2013-6-16 点击量:

    一、题目描述:



    若是一小我在知道了股票天天的股价今后,对该股票进行投资,问什么时辰买入和卖出能取得大收益。其数学模型就是,给定一个整数数组,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;
    forint i = 0; i < length-1; i++) {
    forint 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 diff = 0;
    forint i = 1; i < len; i++) {
    diff
    = diff >= 0 ? diff + arr[i] - arr[i-1] : arr[i] - arr[i-1];
    }
    return diff;
    }




     

    在碰到很多须要O(n)错杂度的场合,动态规划老是可以或许获得一个斗劲简单的解答。

     

     

     

     
    我所有的自负皆来自我的自卑,所有的英雄气概都来自于我的软弱。嘴里振振有词是因为心里满是怀疑,深情是因为痛恨自己无情。这世界没有一件事情是虚空而生的,站在光里,背后就会有阴影,这深夜里一片寂静,是因为你还没有听见声音。—— 马良《坦白书》
    分享到: