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

    添加时间: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;  

            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 diff = 0;  

            for（int i = 1; i < len; i++） {  

            diff     = diff >= 0 ？ diff + arr[i] - arr[i-1] : arr[i] - arr[i-1];  

        }  

            return diff;  

    }




     

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

     

     

     

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