无序数组求最大差值

　　一个数组a[0...n-1]，求a[j]-a[i]的最大值，其中i<j。

　　cite:http://mars914.iteye.com/blog/1667259

第一种方法：

　　从左往右求下标0到 k - 1 的最小值MIN 从右往左求下标k到n -1 的最大值MAX，对于每个k都有一个MAX - MIN的值，最后求这个值的最大值即可。

　　例如数组：4 5 2 6 3 1

　　K：1 2 3 4 5

　　MIN： 4 4 2 2 2

　　MAX：6 6 6 3 1

　　MAX - MIN，最大的值为6 - 2 = 4，即为结果

第二种方法：

　　令b[j] = a[j + 1] - a[j]，

　　那么a[j] - a[i]=(a[i+1]-a[i])+(a[i+2]-a[i+1])+...+(a[j]-a[i-1])

= b[i] +b[i+1]+ ...+ b[j - 1]，

　　即将问题转化成求一个数组子序列的最大值。这个过程的算法是有O(n)的算法的。

时间： 2024-09-28 21:02:33

无序数组求最大差值的相关文章

如何删除多维数组里面的一个值求大神解答

问题描述如何删除多维数组里面的一个值求大神解答想删除 subCats 里面的 [Did] 要如何做在网上找了好多资料但是不会用求大神解答下 $cats var_export如下 array ( 0 => array ( 'id' => '907362758', 'name' => '新品专区', 'subCats' => array ( ), ), 1 => array ( 'id' => '907362759', 'name' => '保暖上装',

【c语言】2维数组求平均值，指针出问题了

问题描述 [c语言]2维数组求平均值,指针出问题了 double average(double (*p)[],double *q,int n,int m) { int i,j; double NU,AE;//每列总和与每行总和 for(i=0;i<n;i++) { for(NU=0,j=0;j<m;j++) { NU+=(*p+i)[j];//每列的和 } q[i]=NU/m;//每行的平均值 AE+=NU;//每行的和 } return AE/(n*m);//总平均值 } 第一行的平均值没错

new-[JAVA]数组求代码解释

问题描述 [JAVA]数组求代码解释求代码解释 public class CouponCollector { public static void main(String[] args) { int N = Integer.parseInt(args[0]); boolean[] found = new boolean[N]; int cardcnt = 0; int valcnt = 0; while (valcnt < N) { int val = (int) (Math.random(

c语言-C语言用递归求圆周率的值，要求精确到小数点后3位，不得使用循环

问题描述 C语言用递归求圆周率的值,要求精确到小数点后3位,不得使用循环 C语言用递归求圆周率的值,要求精确到小数点后3位,不得使用循环解决方案 http://jingyan.baidu.com/article/bea41d437c69b8b4c51be6e9.html 解决方案二: public class Test { public static void main(String[] args) { System.out.println("怎么插入代码块.."); } }

php小技巧把数组的键和值交换形成了新的数组,查找值取得键

复制代码代码如下: $cityname = array_flip($city_DB[name]); //把数组的键和值交换形成了新的数组 $city_name = array_search($city_id,$cityname,true); //查找值取得键

Delphi中用ADO求表达式的值的另类方法

Delphi里求表达式的值的另类方法(用ADO) [1]用一个ADOConnectioin1(已经连上一个数据库)和一个ADOQuery1 [2] With ADOQuery1 do close; SQl.clear; SQL.ADD('Select 123+34*11');//只能进行整数运算 Open; Showmessage(IntToStr(Fields[0].AsInteger)); End; 这里可以使用任何SQL内部函数,如果需要特殊,还可以自定义函数.

PHP关联数组实现根据元素值删除元素的方法

本文实例讲述了PHP关联数组实现根据元素值删除元素的方法.分享给大家供大家参考.具体如下: ? 1 2 3 4 5 6 7 <?php $array1 = array("a" => "green", "red", "blue", "red"); $array2 = array("b" => "green"); $result = array_di

php数组索引与键值操作技巧实例分析

本文实例讲述了php数组索引与键值操作技巧.分享给大家供大家参考.具体如下: ? 1 2 3 4 5 <?php $array = array("a", "b","c"); //定义数组 $array[] = "Simon"; //增加一个新的数组元素 print_r($array); //输出数组 ?> ? 1 2 3 4 5 <?php $array = array("a&qu

Perl中怎样从数组中删除某个值

这篇文章主要介绍了Perl中怎样从数组中删除某个值?本文讲解如何把数组的元素赋值为undef,然后在从数组中删除元素,需要的朋友可以参考下我不确定undef是否和从数组中消除值有确切的关系,猜测一下,如果我们将undef视为"空",那么会有一些联系.但通常来说,将某些东西赋值为undef和删除某些东西是不一样的. 首先来看怎样把数组的元素赋值为undef,之后再了解如何从数组中删除元素. 从下面的代码开始: 代码如下: use Data::Dumper qw(Dumper); m