最大化圓形陣列中連續差的總和


難度級別 容易獎學金
經常問 Cadence印度 易趣 GE醫療集團 卡拉特 Quora的 SAP實驗室 方形
排列 貪婪 排序

問題陳述

假設您有一個 整數 排列。 該數組應視為 圓形陣列。 數組的最後一個值將連接到第一個數組,n ⇒a1。 問題“最大化圓形陣列中的連續差之和”要求找出每個連續元素之間的差之和。 因此,您必須找到連續元素之間的差異。 您可以重新排列陣列編號。 這樣它們的差異之和應該最大。

最大總和= | a1 – a2 | + | a3 – a4 | + | 一種n-1 – 一個n | + | 一種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是數組的實際長度。 我們已經聲明了一個稱為輸出的變量。 這將得到數組的差異。 然後將其總結並存儲到輸出中。 但是在遍歷數組之前,我們將對數組進行排序。 我們將對數組進行排序,使其應按升序排列。 後 排序 在數組中,我們數組中編號最低的是數組的開頭。 數組中更大的數字位於數組的末尾。

由於我們已經對數組進行了排序,因此我們只需要遍歷數組就可以達到數組長度的一半。 然後,我們得到數組當前值和輸出值的兩倍之差,並將其存儲到輸出中。 在這種情況下,我們得到差值,然後得到數組的最後一個值,即它的值的兩倍。 然後將輸出值相加並將其存儲在輸出中。 繼續進行此過程,直到達到數組長度的一半,然後返回輸出值。

推薦碼

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) 哪裡 “ n” 是數組中元素的數量。 因為我們已經對數組進行了排序。 因此,時間複雜度變得像合併排序那樣。 由於這標誌著時間複雜度的上限。

空間複雜度

O(1) 因為不需要額外的空間。 因此,算法所需的空間複雜度是恆定的。 但是整個程序的空間複雜度是線性的。