两种方法求解 正数数组中 两个数相减 的最大值-阿里云开发者社区

开发者社区> 技术mix呢> 正文

两种方法求解 正数数组中 两个数相减 的最大值

简介:
+关注继续查看

一,问题描述

给定一个正数数组arr(即数组元素全是正数),找出该数组中,两个元素相减的最大值,其中被减数的下标不小于减数的下标。

即求出: maxValue = max{arr[j]-arr[i] and j >= i}

 

二,求解思路

下面采用两种不同的算法来求解,第一种算法的时间复杂度为O(N),第二种算法的时间复杂度为O(N^2)。

算法一思路如下:(初始时减数为arr[0],然后算法不断记录比当前减数更小的减数)

maxValue初始化为0,因为当 i==j 时,arr[j] - arr[i] = 0,故 maxValue的值不可能为负数。

因此将下标 i 初始化为0,j 从下标1处开始向后扫描,并计算sub = arr[j]-arr[i]

若sub大于maxValue,则更新maxValue的值。

否则,若sub小于0,意味着找到一个新的数组元素,该数组元素比 arr[i]的值要小,则更新下标 i.

 

为什么这样可以?

因为:当计算 sub = arr[j]-arr[i]时,arr[i]越小,则得到的sub越大。而下标 i 不断标记更小的减数,后面的元素arr[j]与 更小的减数相减才能得到更大的差值。

比如,下图所示数组:

 

arr[0]=18,当j=2时,max=arr[2]-arr[0]=8。当遍历到arr[3]=12时,由于12小于18,故把下标 i 由 0 更新为 3。不需要”关注“下标为1和2的这两个元素。因为,

若在 j>3 后面有元素使得 arr[j]-arr[1] 或者 arr[j]-arr[2]>maxValue,则该arr[j]-arr[0]一定比 arr[j]-arr[1]更大,因为arr[1]和 arr[2]都比arr[0]大。

同理:也不需要关注元素值为12 和 元素值为10之间的元素,因为,若后面某个元素减去某个 “12 到 10之间的元素(16、18、22)”比maxValue大,那么它减去12一定更大

这样,下标 i 记录的总是下一个比 arr[i] 更小的值(这有点类似于贪心算法的味道,每次总是贪比当前值更小的一个值,而不是如算法2中那样依次遍历数组中的每个元素。

 

代码如下:

复制代码
 1     //算法复杂度O(N). 找出数组arr中两个数相减的最大值
 2     public static int maxValueOfSubtraction(int[] arr){ 
 3         int max = 0;// when j == i
 4         int i = 0;
 5         int sub;
 6         for(int j = 1; j < arr.length; j++){
 7             sub = arr[j] - arr[i];
 8             if(sub > max)
 9                 max = sub;
10             else if(sub < 0)//means there is a number smaller than a[i](i initial value is 0)
11                 i = j;
12         }
13         return max;
14     } 
复制代码

 

算法二:

就是一个很普通的方法。求出 数组中所有下标大的元素减去下标小的元素,找出其中的最大值即可。代码如下:

复制代码
 1     //O(N^2) 找出数组arr中两个数相减的最大值
 2     public static int maxValueSub(int[] arr){
 3         int max = 0;
 4         int sub;
 5         for(int i = 0; i < arr.length; i++){
 6             for(int j = i+1; j < arr.length; j++){
 7                 sub = arr[j] - arr[i];
 8                 if(sub > max)
 9                     max = sub;
10             }
11         }
12         return max;
13     }
复制代码

 

一个错误的解法:

由于题目中要求的是 被减数的下标要大于减数的下标,故下面解法是错误的:

依次扫描数组中的每个元素,找出数组元素中的最大值和最小值。最大值减去最小值 即为两个元素相减的最大值。

错误的原因是:最大值元素的下标 可能 比 最小值元素的下标要小。

错误解法代码如下:

复制代码
 1     public static int maxValueSub3(int[] arr){
 2         int min, max;
 3         int indexM = -1;int indexm = -1;
 4         min = max = arr[0];
 5         for(int i = 1; i < arr.length; i++){
 6             if(arr[i] > max)
 7             {
 8                 max = arr[i];
 9                 indexM = i;
10             }
11             else if(arr[i] < min){
12                 min = arr[i];
13                 indexm = i;
14             }
15         }
16         System.out.println("indexM" + indexM + " indexm:" + indexm);
17         return max - min;
18     }
复制代码

 

三,运行时间的比较

采用 这篇文章 中提到的随机数生成算法 来随机生成一个数组,然后比较上面两个算法的运行时间。

机器环境如下:

OS:win7 64bit、RAM:6GB、CPU:Pentium(R)Dual-Core E5800@3.2GHz

时间比较如下:

数组大小        算法1运行时间       算法2运行时间

100*100               1                        61

200*100               3                        158

400*100               2                        568

500*100               2                        878

100*100*10         4                        3451

 

整个代码如下:

复制代码
 1 /*
 2  * given an array, find out the max value of two numbers's distraction.
 3  * max{a[j]-a[i]} under the condition of j>=i
 4  */
 5 public class MaxValue {
 6     
 7     //算法复杂度O(N). 找出数组arr中两个数相减的最大值
 8     public static int maxValueOfSubtraction(int[] arr){ 
 9         int max = 0;// when j == i
10         int i = 0;
11         int sub;
12         for(int j = 1; j < arr.length; j++){
13             sub = arr[j] - arr[i];
14             if(sub > max)
15                 max = sub;
16             else if(sub < 0)//means there is a number smaller than a[i](i initial value is 0)
17                 i = j;
18         }
19         return max;
20     } 
21     
22     //O(N^2) 找出数组arr中两个数相减的最大值
23     public static int maxValueSub(int[] arr){
24         int max = 0;
25         int sub;
26         for(int i = 0; i < arr.length; i++){
27             for(int j = i+1; j < arr.length; j++){
28                 sub = arr[j] - arr[i];
29                 if(sub > max)
30                     max = sub;
31             }
32         }
33         return max;
34     }
35     
36     
37     public static void main(String[] args) {
38         int[] arr = C2_2_8.algorithm3(100*100*10);
39 
40         long start = System.currentTimeMillis();
41         int r = maxValueOfSubtraction(arr);
42         long end = System.currentTimeMillis();
43         System.out.println("maxValue=" + r + "  O(N)'s time:" + (end -start));
44         
45         long start2 = System.currentTimeMillis();
46         int r2 = maxValueSub(arr);
47         long end2 = System.currentTimeMillis();
48         System.out.println("maxValue=" + r2 + "  O(N^2)'s time:" + (end2 - start2));
49     }
50 }


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10062 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
11605 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
9157 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13875 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4498 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7361 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
22382 0
+关注
2969
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载