循環配列の連続する差の合計を最大化する


難易度 簡単に
よく聞かれる ケイデンスインド オークション GEヘルスケア カラット Quora SAPラボ 正方形である
配列 貪欲 並べ替え(ソート)

問題文

あなたが持っているとしましょう 整数 配列。 この配列は、 円形配列。 配列の最後の値は、最初の配列に接続されます。n ⇒a1。 「循環配列の連続する差の合計を最大化する」という問題は、連続する各要素間の差の最大合計を見つけることを求めています。 したがって、連続する要素間の違いを見つける必要があります。 配列番号を並べ替えることができます。 それらの差の合計が最大になるように。

最大合計= | a1 – a2 | + | a3 – a4 | + | an-1 – an | + | an – 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という変数を宣言しました。 これにより、配列の違いがわかります。 そして、それを合計して、出力に保存します。 ただし、配列をトラバースする前に、配列を並べ替えます。 昇順になるように配列を並べ替えます。 後 並べ替え 配列の中で最も小さい番号の配列は、配列の先頭にあります。 そして、配列内の大きい方の数は、配列の最後にあります。

配列をソートしたので、配列の長さの半分まで配列をトラバースする必要があるだけです。 次に、配列の現在の値と出力値のXNUMX倍の差を取得し、それを出力に格納します。 これで差を取得し、次に配列の最後の値、つまりその値のXNUMX倍を取得します。 そして、出力値を合計して出力に保存します。 配列の長さの半分に達するまでこのプロセスを続行し、出力の値を返します。

コード

循環配列の連続する差異の合計を最大化する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) where 「n」 配列内の要素の数です。 配列を並べ替えたからです。 したがって、時間計算量はマージソートのようになります。 それは時間計算量の上限を示しているからです。

スペースの複雑さ

O(1) 余分なスペースは必要ありません。 したがって、アルゴリズムに必要なスペースの複雑さは一定です。 しかし、プログラム全体のスペースの複雑さは線形です。