問題
Take every contiguous window of span digits and multiply its digits. Return the largest product. Leading zeros are ordinary digits; a window containing zero has product zero. Do not reorder or skip digits.
Implement largest_adjacent_digit_product(digits, span).
Input
digits: The digit sequence, including any leading zeros.
span: The exact number of adjacent digits in a window.
Output
Return the greatest product over all windows of this width.
制約
1 ≤ digit-string length ≤ 100,000. Characters are 0…9. 1 ≤ span ≤ min(18, length). All products fit signed 64-bit.
例
入力：
span = 2
digits = "23405"
期待される出力：
expected = 12入力：
long long span = 2;
std::string digits = "23405";
期待される出力：
long long expected = 12;入力：
long span = 2;
string digits = "23405";
期待される出力：
long expected = 12;解説
The windows 23, 34, 40, and 05 have products 6, 12, 0, and 0. The largest is 12.
入力：
span = 3
digits = "102"
期待される出力：
expected = 0入力：
long long span = 3;
std::string digits = "102";
期待される出力：
long long expected = 0;入力：
long span = 3;
string digits = "102";
期待される出力：
long expected = 0;解説
There is only one width-three window. It contains zero, so 1 × 0 × 2 = 0.
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
窓の中に0があると積は0になるので、最大値候補は連続した非0区間だけです。
ヒント 2
毎回最初から掛け直さないように、スライディングウィンドウか区間ごとの積を使います。
ヒント 3
桁数の条件に注意してください。先頭の0も桁数に含まれ、非0区間より長い窓は積が0です。
目安の計算量
時間 O(n)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。