java - 归并排序应用

Question

我正在做一个练习，给定一个包含 N 个值的数组，我需要得到两个数字，它们的减法(最高 - 最低)是最正数。我希望 v 大于 c...情况是...假设我想以 C 的价格购买拍卖品，以便我可以以 V 的价格出售它们并获得最大利润，数组的每个单元格是t 天那次拍卖的价格，所以我想以尽可能低的价格购买，以便我可以以尽可能高的价格出售，因此 C 必须出现在数组中的 V 之前。例如:

n = 8
arr = {6,7,3,8,9,2,1,4,20}

我想要 c = 1 和 v = 20，因为 20 - 1 = 19(这意味着这 2 个数字的减法是最高)

另一个例子:

n = 6
arr = {8,12,45,40,18,29}

我想要 c = 8 和 v = 45 因为它们的减法是所有其他减法中最大的。 (我想澄清一下，c 并不总是数组中最小的数字)。两个数字不需要彼此相邻。如果我有 n = 1, {1} 那么 c = 1 和 v = 1。

此示例演示 c 和 v 并不总是最低/最高值。

n = 6
arr = {19,27,5,6,7,8}

在这种情况下 c = 19 和 v = 27

此外，我需要使用许多合并排序的代码来解决这个问题(示例将其分为两种方法:mergesort 处理递归，merge 处理使用辅助数组的位置)。

我正在使用合并排序代码(我认为合并是不必要的，因为我不关心排序)，到目前为止我有以下代码，但它显然是错误的，有人可以告诉我我没有做什么对吧？

public static void mergeSort(int start, int end) {
    if(start < end) {
        int half = (start + end) / 2;
        mergeSort(start, half);
        for(int i = start; start < half; start++, i++){
            if((arr[i+1] - arr[i]) > temp){
                temp = arr[i+1] - arr[i];
                c = i;
                v = i+1;
            }
        }
        mergeSort(half+1, end);
        for(int i = half+1; i < end; half++, i++){
            if((arr[i+1] - arr[i]) > temp){
                temp = arr[i+1] - arr[i];
                c = i;
                v = i+1;
            }
        }
    }
}

在此先感谢您提供的任何帮助!

Answer 1

我猜你的代码中的名称 mergeSort 是继承的....

因为你已经进行了递归，所以没有必要遍历所有的元素，因为递归之后，结果已经呈现出来了。例如，一种可能的方法是将最小值交换到第一个位置，将最大值交换到最后一个位置，然后，在递归的“上层”级别上，您可以直接检索它们。

---

这是另一个利用合并排序原理的解决方案，但仅返回最大值。

public class test {
    static int arr [] = {6,7,3,8,9,2,1,4,20};

    public static void main (String args[]) {
        System.out.println(merge_select_max(0, arr.length - 1));
    }

    public static int merge_select_max (int start, int end) { // both inclusive
        if (start == end) {
            return arr[start];          
        }
        else {
            int half = (start + end) / 2;
            int first = merge_select_max (start, half);
            int second = merge_select_max (half + 1, end);
            return (first > second ? first : second);           
        }       
    }
}