Geek asks and answers

Merge Sort Application

I am doing an exercise when an array of N values ​​is given, I need to get two numbers, that subtracting them (the highest - the lowest) is the most positive number. I want v to be more than c ... The thing is ... let's say I want to buy auctions at price C, so I can sell them at price V and get the maximum profit, and each cell in the array is priced at auction on day t, so I want to buy at the lowest price, so I can sell at the highest price, so C should appear before V in the array. For instance:

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

I want c = 1and v = 20because 20 - 1 = 19(this means that subtracting from these two numbers is the highest)

Another example:

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

I want c = 8and v = 45because their subtraction is the highest number of all other subtractions. (I want to clarify that c is not always the smallest number in an array). Both ROOMS DO NOT NEED TO BE NEXT FOR OTHER OTHERS. If I have n = 1, {1}, then c = 1and v = 1.

This example demonstrates that c and v are not always the smallest / highest values.

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

In this case, c = 19andv = 27

In addition, I need to solve this problem using the merge sort method (examples divide it into two methods: mergesort, which handles recursions, and merge, which performs a position change using the aux array).

mergesort ( , , ), , , , , - , ?

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

, !

+3
1

, mergeSort ....

, , , . , , "" .

, merge-sort, 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);           
        }       
    }
}
+2

More articles:


All Articles