纷纷扰扰的世界有很多强迫症，我就是一个爱吃香蕉的强迫症，我去水果店买香蕉，按筐买，我的要求是买回来的每一筐必须有相同数量的香蕉，我通常的做法是：
<1>取出筐里的一部分香蕉不要
<2>整筐香蕉都不要
那你知道我最多能买到多少香蕉呢？
举列：
水果店每个筐里的香蕉：【1】【2】【3】，则最多买到香蕉：4个
水果店每个筐里的香蕉：【5】【0】【29】【14】，则最多买到香蕉数：29个
问题解析：
1. 按筐里的香蕉个数进行排序。
例如：水果店每个筐里的香蕉：【5】【0】【29】【14】，排序后为：【0】【5】【14】【29】
2. 根据排序结果，从小到大选择筐中香蕉个数，来计算每次选择能买到的最多香蕉数。
选择方案如下：
<1>选择在筐里装【0】个香蕉，则最多能买到0个香蕉
<2>选择在筐里装【5】个香蕉，则舍弃第一筐，买走第二筐【5】，第三筐买走5根，其余舍弃，第四筐买走5根，其余舍弃，则最多能买到的香蕉数为：5 + 5 + 5 = 15
<3>选择在筐里装【14】根香蕉，则舍弃第一框，第二筐，买走第三筐【14】，第四筐买走14根，其余舍弃，则最多能买到的香蕉数为：14 + 14 = 28
<4>选择在筐里装【29】根香蕉，则舍弃第一筐，第二筐，第三筐，买走第四框【29】，则最多能买到的香蕉数为：29
所有选择方案中，能买到的最多香蕉数为29
3. 数据模型
假设水果店有10筐香蕉，我们将每筐的香蕉数对应放到一个数组a中，即：a = [0, 5, 14, 28, 6, 9, 9, 29, 11, 17]，a.length = 10
对数组a进行排序：[0, 5, 6, 9, 9, 11, 14, 17, 28, 29]
依次选择a数组中的每个元素，作为选择买走的每筐香蕉数：(max表示能买到的最大香蕉数)
选择筐里装a[0]根香蕉，则max₀ = a[0] * (a.length - 0)
选择筐里装a[1]根香蕉，则max₁ = a[1] * (a.length - 1)
选择筐里装a[2]根香蕉，则max₂ = a[2] * (a.length - 2)
...
选择筐里装a[i]根香蕉，则maxᵢ = a[i] * (a.length - i)
注意：
这里有个问题：a数组中含有重复的元素9，9，如果按上面的规则：
第一个9，对应a[3]，则max₃ = a[3] * (a.length - 3) = 63
第二个9，对应a[4]，则max₄ = a[4] * (a.length - 4) = 54
而实际的情况是选择筐里装9根香蕉时，能买走的最大香蕉数是相等的，都为63，
但此问题不影响最终计算买到最大香蕉数的这个结果。
解决：
针对于第二个重复元素问题，我们可以借助map结构进行处理：
key = a[i]，value = maxᵢ
对于选择数组a中的元素a[i]，先判断是否在map中，若存在，则从map中获取值并赋值给maxᵢ，否则将计算得到的maxᵢ放到map中。
代码实现
对数组a使用快速排序，然后遍历数组a，依次计算并比较，最终得出能买到最多的香蕉数。
（数组a中的重复元素，不影响最终结果，因此忽略对其特殊处理）
public static int getMaxBananaNumber(int[] a) {
if (a == null) {
return 0;
}
if (a.length == 1) {
return a[0];
}
quickSort(a, 0, a.length - 1);
int max = 0;
for (int i = 0,len = a.length; i < len; i++) {
max = Math.max(a[i] * (len - i), max);
}
return max;
}
public static void quickSort(int[] a, int start, int end) {
if (start < end) {
int mid = partition(a, start, end);
quickSort(a, start, mid-1);
quickSort(a, mid+1, end);
}
}
private static int partition(int[] a, int start, int end) {
int i = start - 1;
int p = a[end];
for (int j = start; j <= end-1; j++) {
if (a[j] <= p) {
i++;
exchange(a, i, j);
}
}
exchange(a, i+1, end);
return i+1;
}
private static void exchange(int[] a, int frontIndex, int laterIndex) {
int temp = a[frontIndex];
a[frontIndex] = a[laterIndex];
a[laterIndex] = temp;
}
