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

一,难题讲述

给定几个正数数组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 韦斯著 书中第壹七页 二.28题中并未建议数组arr中的成分不通重复。

 

2,求解思路

有三种思路,壹种是对数组中的各种成分,求出该因素与它背后成分的和,然后记录下最大的。

如,对于下标为 i 的因素,for each j belongs to [i+一,
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算法贰运维时刻(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     }

 

再扩充一下:还是能总计七个数相加的最大值。照旧一如既往的思绪,当境遇比上2回运算中的
加数
更大的数时,则把该数替换掉原来加数中细小的不得了加数。(三数相加,视为有八个加数。。。^-^)

再扩张一下,是或不是深感到这几个题材和
求解最大子类别和
有点联系了?  二者都是一向跳过好几不供给“关怀”的要素,并连接“贪心”出
下多少个候选元素。

 

完全代码如下:

 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 }

 

相关文章