归并排序应用

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 是继承的......

由于您已经进行了递归，因此无需迭代所有元素，因为 after 递归，结果已经呈现。例如，一种可能的方法是将最小值交换到第一个位置，将最大值交换到最后一个位置，然后，在递归的“上”级别上，您可以直接检索它们。

---

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

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);           
        }       
    }
}