2016校招真题之最大差值

1、题目描述

有一个长为n的数组A，求满足0≤a≤b<n的A[b]-A[a]的最大值。给定数组A及它的大小n，请返回最大差值。

测试样例：

[10,5],2

返回：0

2、代码实现

 1 package com.wcy.october;
 2 
 3 /**
 4  * 时间：2016年10月15日
 5  * 题目：有一个长为n的数组A，求满足0≤a≤b<n的A[b]-A[a]的最大值。给定数组A及它的大小n，请返回最大差值。
 6  * 测试样例：[10,5],2 返回：0
 7  */
 8 public class LongestDistance {
 9     
10     /**
11      * 用户页面测试
12      * @param args
13      */
14     public static void main(String[] args) {
15         LongestDistance test = new LongestDistance();
16         String str = "[10,5],2";
17         int[] arrs = test.getArrs(str);
18         int result = test.getDis(arrs,arrs.length);
19         System.out.println(result);
20     }
21     
22     /**
23      * 输入的字符串转换成数组格式
24      * @param str 字符串
25      * @return 转换之后的数组
26      */
27     public int[] getArrs(String str){
28         str = str.replaceAll("\[", "");
29         str = str.replaceAll("\]", "");
30         String[] strs = str.split(",");
31         int[] arrs = new int[strs.length-1];
32         for (int i = 0; i < strs.length-1; i++) {
33             arrs[i] = Integer.parseInt(strs[i]);
34         }
35         return arrs;
36     }
37     
38     /**
39      * 求最大差值
40      * @param A 输入的数据数组
41      * @param n 数组的大小
42      * @return 最大差值
43      */
44     public int getDis(int[] A, int n) {
45         int tempMaxNum = 0;
46         for (int i = 0; i < A.length; i++) {
47             for (int j = i+1; j < A.length; j++) {
48                 if ((A[j]-A[i]) > tempMaxNum) {
49                     tempMaxNum = A[j]-A[i];
50                 }
51             }
52         }
53         return tempMaxNum;
54     }
55 }

3、另外代码实现，但是不符合牛客网提交要求，不过结果符合的。

 1 package com.wcy.october;
 2 
 3 /**
 4  * 时间：2016年10月15日
 5  * 题目：有一个长为n的数组A，求满足0≤a≤b<n的A[b]-A[a]的最大值。给定数组A及它的大小n，请返回最大差值。
 6  * 测试样例：[10,5],2 返回：0
 7  */
 8 public class LongestDistance3 {
 9     
10     /**
11      * 用户页面测试
12      * @param args
13      */
14     public static void main(String[] args) {
15         String str = "[10,5,11],2";
16         String[] strs = LongestDistance3.getArrs(str);
17         int result = LongestDistance3.getLongestDistance(strs);
18         System.out.println(result);
19     }
20     
21     /**
22      * 输入的字符串转换成数组格式
23      * @param str 字符串
24      * @return 转换之后的数组
25      */
26     public static String[] getArrs(String str){
27         str = str.replaceAll("\[", "");
28         str = str.replaceAll("\]", "");
29         String[] strs = str.split(",");
30         return strs;
31     }
32     
33     /**
34      * 求最大差值
35      * @param arrs 数值
36      * @param sizeNum 数组大小
37      * @return 最大差值
38      */
39     public static int getLongestDistance(String[] strs){
40         int tempMaxNum = 0;
41         for (int i = 0; i < strs.length-1; i++) {
42             for (int j = i+1; j < strs.length-1; j++) {
43                 if ((Integer.parseInt(strs[j])-Integer.parseInt(strs[i])) > tempMaxNum) {
44                     tempMaxNum = Integer.parseInt(strs[j])-Integer.parseInt(strs[i]);
45                 }
46             }
47         }
48         return tempMaxNum;
49     }
50     
51 }