C++で数値内のM個の連続する桁の最大和と最大積を求める方法

この問題では、数値を表す文字列が与えられます。C++を用いて、その数値の中からM個の連続する桁で構成される部分列をすべて調べ、和と積がそれぞれ最大となる値(maxSum・maxProd)を求めるプログラムを作成します。

問題の概要

数値からM個の連続する桁で構成されるすべての部分列を抽出し、その中で最大の和と最大の積を返します。

具体例を使って問題を確認してみましょう。

入力

number = 2379641, M = 4

出力

maxSum = 26
maxProd = 1512

説明

サイズ4の連続する部分列は「2379」「3796」「7964」「9641」の4つです。

maxSum = 7 + 9 + 6 + 4 = 26
maxProd = 7 × 9 × 6 × 4 = 1512

解法のアプローチ

最もシンプルな解法は、数値からサイズMの連続する部分列をすべて取り出し、それぞれの桁の値を加算・乗算して、全結果の中から最大の和と積を求める方法です。

具体的には、外側のループで部分列の開始位置を1つずつずらしながら、内側のループでM個の桁を順に処理します。各部分列ごとに和と積を計算し、これまでの最大値と比較して更新していきます。計算量はO(N×M)となります。

実装例

以下は、この解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;
int findMaxVal(int x, int y){
   if(x > y)
      return x;
      return y;
}
void calcMaxProductAndSum(string number, int M){
   int N = number.length();
   int maxProd = -1, maxSum = -1;
   int product = 1, sum = 0;
   for (int i = 0; i <= N - M; i++){
      product = 1, sum = 0;
      for (int j = i; j < M + i; j++){
         product = product * (number[j] - '0');
         sum = sum + (number[j] - '0');
      }
      maxProd = findMaxVal(maxProd, product);
      maxSum = findMaxVal(maxSum, sum);
   }
   cout<<"The Maximum Product of "<<M<<" consecutive digits in number "<<number<<" is "<<maxProd<<endl;
   cout<<"The Maximum Sum of "<<M<<" consecutive digits in number "<<number<<" is "<<maxSum;
}
int main() {
   string str = "2379641";
   int m = 4;
   calcMaxProductAndSum(str, m);
}

なお、外側のループの継続条件は「i <= N - M」とすることで、末尾の部分列(この例では「9641」)も漏れなく走査できます。

出力結果

The Maximum Product of 4 consecutive digits in number 2379641 is 1512
The Maximum Sum of 4 consecutive digits in number 2379641 is 26

このように、文字列として与えられた数値からM個の連続する桁を順に走査するだけで、最大和と最大積を簡単に求めることができます。