C++で部分配列の全要素にXを掛けた後、部分配列の和を最大化する方法

問題の概要

ここでは、整数型の配列と整数変数「X」が与えられます。まず、与えられた配列から部分配列を作成し、次にその部分配列のすべての要素に整数Xを掛け合わせます。最終的に、最大の和を構成する要素を見つけ出すことが目的です。

入出力シナリオ

入力 − int arr[] = {2, 4, 1, -5, -2}, X = 3

出力 − 任意の部分配列の全要素にXを掛けた後の部分配列和の最大値：21

説明 − 配列と整数変数Xが与えられています。まず、配列から部分配列として {2, 4, 1} を取り出します。次に、この部分配列の全要素にX(=3)を掛けると、配列は {6, 12, 3, -5, -2} になります。最後に最大部分配列和を求めると、6 + 12 + 3 = 21 となります。

入力 − int arr[] = {-1, 2, -6, 3, -4}, X = -1

出力 − 任意の部分配列の全要素にXを掛けた後の部分配列和の最大値：11

説明 − 配列と整数変数Xが与えられています。まず、配列から部分配列 {-1, -6, -4} を取り出します。次に、この部分配列の全要素にX(=-1)を掛けると、配列は {1, 2, 6, 3, 4} になります。最後に最大部分配列和を求めると、1 + 6 + 4 = 11 となります。

プログラムで使用しているアプローチ

• 整数配列と整数変数「X」を入力として受け取ります。配列のサイズを計算し、そのデータを関数 Max_Subarray(arr, size, x) に渡します。

• 関数 Max_Subarray(arr, size, x) の内部処理

  • 配列 int arr_2[size][3] と一時変数 temp(初期値 0)を宣言します。

  • C++の memset() メソッドを使用して、配列「arr_2」のすべての要素を -1 で初期化します。

  • i を 0 から配列サイズまでループさせます。ループ内では、temp に関数 max(temp, check(i, 0, arr, arr_2, size, x)) の呼び出し結果を設定します。

  • temp を返します。

• 関数 int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x) の内部処理

  • 一時変数 count を 0 で宣言します。

  • first == size の場合、0 を返します。

  • arr_2[first][last] != -1 の場合、arr_2[first][last] を返します(メモ化により計算済みの結果を再利用)。

  • last == 0 の場合、C++の組み込み max 関数を呼び出して最大値を求めます。具体的には、max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x)) を計算し、さらに count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x)) を設定します。

  • それ以外で last == 1 の場合は、count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x)) とし、count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x)) を設定します。

  • 上記以外の場合は、count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x)) を設定します。

  • arr_2[first][last] に count を格納して返します。

• 結果を出力します。

なお、引数 last は現在の状態を表しており、「0」はまだXを掛ける操作を開始していない状態、「1」は現在Xを掛けている区間の途中である状態、「2」はXを掛ける区間をすでに終了した状態を意味します。この状態管理とメモ化を組み合わせることで、重複する計算を避けながら効率的に最大値を探索できます。

実装例

#include <bits/stdc++.h>
using namespace std;
#define Max_size 5

int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x){
    int count = 0;
       if(first == size){
          return 0;
       }
       if(arr_2[first][last] != -1){
          return arr_2[first][last];}
       if (last == 0){
          count = max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x));
          count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
       }
       else if(last == 1){
          count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
          count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
       }
       else{
          count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
       }
       return arr_2[first][last] = count;
}
int Max_Subarray(int arr[], int size, int x){
    int arr_2[size][3];
    int temp = 0;
    memset(arr_2, -1, sizeof arr_2);
    for(int i = 0; i < size; i++){
       temp = max(temp, check(i, 0, arr, arr_2, size, x));
    }
    return temp;
}
int main(){
    int arr[] = {2, 4, 1, -5, -2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    cout<<"Maximize the subarray sum after multiplying all elements of any subarray with X are: "<<Max_Subarray(arr, size, x);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が生成されます。

Maximize the subarray sum after multiplying all elements of any subarray with X are: 21