C++
 Computer >> コンピューター >  >> プログラミング >> C++

C++でi

問題概要

整数の配列が与えられたとき、次の式の値を最大化することが目的です。

arr[j]-arr[i] + arr[l]-arr-k(ただし、i<j<k<l は要素のインデックス)

この問題は、すべての要素の組み合わせを走査して式の値を計算し、これまでに見つかった最大値よりも大きい場合はその値を記録していき、最後に最大値を返すことで解くことができます。

入力例

arr[]= { 1,2,3,4 }

出力例

上記の式の最大値 : 2

説明: i<j<k<l を満たすのは i=0, j=1, k=2, l=3 のときです。

arr[j]-arr[i]+arr[l]-arr[k]= 2-1+4-3=1+1=2

入力例

arr[]= { 5,5,5,5,5 }

出力例

上記の式の最大値 : 0

説明: i<j<k<l を満たす任意の i,j,k,l に対して、

arr[j]-arr[i]+arr[l]-arr[k]= 5-5+5-5=0

プログラムで使用するアプローチ

  • 整数型配列 a[] に数値を格納します。

  • 関数 maximizeSum(int arr[], int n) は配列とその長さ n を入力として受け取り、i<j<k<l を満たす arr[j]-arr[i]+arr[l]-arr[k] の最大値を返します。

  • 変数 sum は arr[j]-arr[i] と arr[l]-arr[k] の合計を格納するために使用します。

  • 初期の最大値として maxx=arr[0] を設定します。

  • i=0, j=1, k=2, l=3 から開始し、i<n-3, j<n-2, k<n-1, l<n の範囲で配列を走査します。

  • 各インデックス i,j,k,l について arr[j]-arr[i]+arr[l]-arr[k] を計算し、sum に格納します。

  • 現在の sum が maxx 以上であれば maxx を更新します。

  • 最後に maxx を結果として返します。

計算量について

このアプローチでは4重ループを使用しているため、時間計算量は O(n4) となります。小規模な入力には有効ですが、大規模な配列に対しては効率化(動的計画法など)を検討する必要があります。

コード例

#include <bits/stdc++.h>
using namespace std;
// 選択した数値の合計を最大化する関数
int maximizeSum(int arr[], int n) {
    int sum=0;
    int maxx=arr[0];
    for(int i=0;i<n-3;i++)
        for(int j=i+1;j<n-2;j++)
            for(int k=j+1;k<n-1;k++)
            for(int l=k+1;l<n;l++){
        sum=arr[j]-arr[i]+arr[l]-arr[k];
        if(sum>=maxx)
            maxx=sum;
    }
    return maxx;
}
int main(){
    int a[] = {5, 3, 9, 2, 20};
    int n = sizeof(a) / sizeof(a[0]);
    cout <<"Maximized value is :"<< maximizeSum(a, n);
    return 0;
}

出力

Maximized value is :24
  1. C++でa+b+c=dを満たす最大のdを配列から見つける方法

    整数の集合が与えられたとき、d = a + b + c を満たす数 d を見つけ、その値を最大化することが目標です。ここで重要なのは、a、b、c、d のすべてが集合内に存在していなければならないという点です。集合の要素数は最小1個、最大1000個であり、各要素は有限の数であるものとします。例えば、集合が {2, 3, 5, 7, 12} の場合、12 = 2 + 3 + 7 と表現できるため、最大の d は 12 となります。解法のアプローチ：ハッシュテーブルを活用するこの問題は、ハッシュテーブル（ハッシュマップ）の手法を使うことで効率的に解くことができます。基本的な考え方は以下の通りです。ま

  2. C++で n! mod (k^x) = 0 となる最大の x を求める方法

    2つの整数 n と k が与えられたとき、n! mod (k^x) = 0 を満たす最大の x の値を求める問題を考えます。例えば n = 5、k = 2 の場合、答えは 3 になります。これは n! = 120 であり、x の各値に対する剰余を計算すると次のようになるためです。120 mod 2^0 = 0、120 mod 2^1 = 0、120 mod 2^2 = 0、120 mod 2^3 = 0、120 mod 2^4 = 8、120 mod 2^5 = 24、120 mod 2^6 = 56、120 mod 2^7 = 120剰余が 0 となる最大の x は 3 であるため、出力は