在O(N)时间内求解 正数数组中 两个数相加的 最大值

时间：2021-09-08 17:15:43

一，问题描述

给定一个正数数组arr（即数组元素全是正数），找出该数组中，两个元素相加的最大值，其中被加数的下标大于加数的下标。由加法运算的可逆性，j >i 这个条件可以去掉。

即求出： maxValue = max{arr[j]+arr[i] and j > i} 

在数组arr中没有重复的元素情况下，若被加数的下标可以等于加数的下标，则该问题变成了寻找正数数组arr中最大值的元素了。因为 max{arr[i]} + max{arr[i]} 一定比 max{arr[i]} + arr[j] 大，其中arr[j]为数组中的任意某个元素。

而《数据结构与算法分析 Java语言描述》Mark Allen Weiss著 书中第37页 2.28 题中并没有指出数组arr中的元素不通重复。

 

二，求解思路

有两种思路，一种是对数组中的每个元素，求出该元素与它后面元素的和，然后记录下最大的。

如，对于下标为 i 的元素，for each j belongs to [i+1, arr.length)需要求出 sum=arr[i]+arr[j] 其中，i belongs to [0,arr.length) and j >=i

这算法的时间复杂度为O(N^2)

第二种思路是，先将加数初始化为下标为0的那个元素（arr[i]=arr[0]），然后，j 往后扫描，若遇到比arr[i]大的元素，则下标 i=j。也就是说，i 总是记录比当前arr[i]更大的元素（贪心思想）。

更详细的解释，类似于这篇文章

代码如下：

 1     //O(N). find out the max sum of two numbers in a positive array
 2     public static int maxSum(int[] arr){
 3         int i = 0;
 4         int max = 0;//数组中所有的元素都是正数
 5         int addValue;
 6         for(int j = 1; j < arr.length; j++){
 7             addValue = arr[i] + arr[j];
 8             if(addValue > max)
 9                 max = addValue;
10             if(arr[j] - arr[i] > 0)
11                 i = j;//记录更大的arr[i]
12         }
13         return max;
14     }

 

三，运行时间的比较

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

机器环境如下：

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

时间比较如下：

数组大小        maxSum运行时间(O(N))       maxSum2算法2运行时间(O(N^2))

100*100             1                                        27

200*100             1                                        68

300*100             2                                        133

500*100             3                                        359

 

此外，按照同样的思路，也可以求解两个数相加的最小值了，哈哈。。。。

求两数相加的最小值，也同样是每次贪心，贪一个较arr[i]更小的值即可，这简直和求解两数相减的最大值一模一样！！！

代码如下：

 1     public static int minSum(int[] arr){
 2         int min = Integer.MAX_VALUE;
 3         int i = 0;
 4         int addValue;
 5         for(int j = 1; j < arr.length; j++){
 6             addValue = arr[j] + arr[i];
 7             if(addValue < min)
 8                 min = addValue;
 9             if(arr[j] - arr[i] < 0)
10                 i = j;
11         }
12         return min;
13     }

 

再扩展一下：还可以计算三个数相加的最大值。还是同样的思路，当碰到比上一次运算中的 加数 更大的数时，则把该数替换掉原来加数中最小的那个加数。（三数相加，视为有三个加数。。。^-^）

再扩展一下，是不是感觉到这个问题和 求解最大子序列和 有点联系了？  二者都是直接跳过某些不需要“关注”的元素，并总是“贪心”出 下一个候选元素。

 

完整代码如下：

 1 public class MaxSum {
 2     
 3     //O(N). find out the max sum of two numbers in a positive array
 4     public static int maxSum(int[] arr){
 5         int i = 0;
 6         int max = 0;//数组中所有的元素都是正数
 7         int addValue;
 8         for(int j = 1; j < arr.length; j++){
 9             addValue = arr[i] + arr[j];
10             if(addValue > max)
11                 max = addValue;
12             if(arr[j] - arr[i] > 0)
13                 i = j;//记录更大的arr[i]
14         }
15         return max;
16     }
17     
18     
19     public static int maxSum2(int[] arr){
20         int max = 0;
21         int addValue;
22         for(int i = 0; i < arr.length; i++){
23             for(int j = i+1; j < arr.length; j++){
24                 addValue = arr[j] + arr[i];
25                 if(addValue > max)
26                     max = addValue;
27             }
28         }
29         return max;
30     }
31     
32     public static void main(String[] args) {
33         int[] arr = C2_2_8.algorithm3(100*100*10);
34 
35         long start = System.currentTimeMillis();
36         int r = maxSum(arr);
37         long end = System.currentTimeMillis();
38         System.out.println("maxValue=" + r + "  O(N)'s time:" + (end -start));
39         
40         long start2 = System.currentTimeMillis();
41         int r2 = maxSum2(arr);
42         long end2 = System.currentTimeMillis();
43         System.out.println("maxValue=" + r2 + "  O(N^2)'s time:" + (end2 - start2));
44     }
45 }

 

标签：

相关文章