【口试】求数组元素最大差值的题目
添加时间: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)错杂度的场合,动态规划老是可以或许获得一个斗劲简单的解答。
我所有的自负皆来自我的自卑,所有的英雄气概都来自于我的软弱。嘴里振振有词是因为心里满是怀疑,深情是因为痛恨自己无情。这世界没有一件事情是虚空而生的,站在光里,背后就会有阴影,这深夜里一片寂静,是因为你还没有听见声音。—— 马良《坦白书》
一、题目描述:
若是一小我在知道了股票天天的股价今后,对该股票进行投资,问什么时辰买入和卖出能取得大收益。其数学模型就是,给定一个整数数组,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)错杂度的场合,动态规划老是可以或许获得一个斗劲简单的解答。