원형 배열에서 연속적인 차이의 합을 최대화


난이도 쉽게
자주 묻는 질문 케이던스 인도 이베이 GE 헬스 케어 캐럿 Quora SAP 연구소 사각형.
배열 탐욕스러운 정렬

문제 정책

당신이 정수 정렬. 이 배열은 원형 배열. 배열의 마지막 값은 첫 번째 배열에 연결됩니다.n ⇒ a1. “원형 배열에서 연속적인 차이의 합을 최대화”라는 문제는 연속 된 각 요소 간의 차이의 최대 합을 찾아야합니다. 따라서 연속 된 요소의 차이를 찾아야합니다. 배열 번호를 재 배열 할 수 있습니다. 차이의 합이 최대가되도록합니다.

최대 합계 = | a1 – a2 | + | a3 – a4 | + | ㅏn-1 – an | + | ㅏn – a1 |

arr[]={9, 8, 4, 2}
22

설명

주어진 배열을 9, 2, 8, 4로 정렬하면

| 9 – 2 | + | 2 – 8 | + | 8 – 4 | + | 4 – 9 | = 22

원형 배열에서 연속적인 차이의 합을 최대화

암호알고리즘

1. Set a variable output to 0.
2. Sort the given array.
3. Traverse up to n/2 length of the array(n is the length of the array).
    1. Sum up the value of output and array’s last values and store it to sum.
    2. Get the difference of output and twice of array’s starting value and store it to the output.
4. Return the value of output.

설명

주어진 정렬 of 정수. 배열은 원형 배열 마지막 요소 바로 뒤의 첫 번째 요소로 이동할 수 있습니다. 연속 요소 간의 차이의 최대 합을 알아 내도록 요청 받았습니다. 그리고 우리는 어레이를 재배치 할 수있는 이점이 있습니다. 차이의 합을 최대화 할 수 있습니다.

여기에 배열이 있습니다. 우리는 실제로 배열을 재배치하지 않을 것입니다. 단순히 숫자를 가지고 놀 수 있습니다. 이제 우리는 배열의 절반 만 횡단 할 것입니다. 이는 배열의 최대 n / 2 길이이며 여기서 n은 배열의 실제 길이입니다. output이라는 변수를 선언했습니다. 배열의 차이를 얻을 수 있습니다. 그리고 그것을 요약하고 출력에 저장하십시오. 그러나 배열을 순회하기 전에 배열을 정렬 할 것입니다. 배열을 오름차순으로 정렬 할 것입니다. 후 정렬 배열에서 가장 낮은 숫자가있는 배열은 배열의 시작 부분에 있습니다. 그리고 배열의 더 큰 숫자는 배열의 끝에 있습니다.

배열을 정렬 했으므로 배열 길이의 절반까지만 배열을 탐색하면됩니다. 그런 다음 배열의 현재 값과 출력 값의 두 배의 차이를 가져와 출력에 저장합니다. 이것에서 우리는 차이를 얻은 다음 배열의 마지막 값을 두 배로 얻습니다. 그런 다음 출력 값을 더하여 출력에 저장합니다. 배열 길이의 절반에 도달 할 때까지이 프로세스를 유지하고 출력 값을 반환합니다.

암호

원형 배열에서 연속적인 차이의 합을 최대화하는 C ++ 코드

#include<iostream>
#include<algorithm>

using namespace std;

int getMaxDiff(int arr[], int n)
{
    int output = 0;

    sort(arr, arr + n);

    for (int i = 0; i < n/2; i++)
    {
        output -= (2 * arr[i]);
        output += (2 * arr[n - i - 1]);
    }

    return output;
}
int main()
{
    int arr[] = { 9, 8, 2, 4 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaxDiff(arr, n) << endl;
    return 0;
}
22

원형 배열에서 연속적인 차이의 합을 최대화하는 Java 코드

import java.util.Arrays;

class maximumDiff
{
    public static int getMaxDiff(int arr[], int n)
    {
        int output = 0;

        Arrays.sort(arr);

        for (int i = 0; i < n/2; i++)
        {
            output -= (2 * arr[i]);
            output += (2 * arr[n - i - 1]);
        }

        return output;
    }
    public static void main (String[] args)
    {
        int arr[] = {9, 8, 2, 4 };
        int n = arr.length;
        System.out.println(getMaxDiff(arr, n));
    }
}
22

복잡성 분석

시간 복잡성

O (n log n) 어디에 "엔" 배열의 요소 수입니다. 배열을 정렬했기 때문입니다. 따라서 시간 복잡성은 병합 정렬과 같습니다. 그것이 시간 복잡성의 상한을 표시하기 때문입니다.

공간 복잡성

O (1) 추가 공간이 필요하지 않습니다. 따라서 알고리즘에 필요한 공간 복잡성은 일정합니다. 그러나 전체 프로그램의 공간 복잡성은 선형 적입니다.