問題描述

小R手上有一個長度為?n?的數組 (n > 0)，數組中的元素分別來自集合?[0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]。小R想從這個數組中選取一段連續的區間，得到可能的最大乘積。

你需要幫助小R找到最大乘積的區間，并輸出這個區間的起始位置?x?和結束位置?y?(x ≤ y)。如果存在多個區間乘積相同的情況，優先選擇?x?更小的區間；如果?x?相同，選擇?y?更小的區間。

注意：數組的起始位置為?1，結束位置為?n。

代碼

from math import log

def solution(n: int, arr: list[int]) -> list[int]:

? ? # Edit your code here

? ? """

? ? 尋找最大乘積區間

? ? Args:

? ? ? ? n: 數組長度

? ? ? ? arr: 輸入數組

? ? Returns:

? ? ? ? 返回最大乘積區間的起始和結束位置 [x, y]

? ? """

? ? # 結果數組，保存起始位置x和結束位置y

? ? result = [1, 1]

? ? # 初始化最大對數和

? ? max_log_sum = float('-inf') if arr[0] == 0 else log(arr[0])

? ?

? ? # 遍歷所有可能的起始位置

? ? for i in range(n):

? ? ? ? # 如果起始位置是0，單獨處理

? ? ? ? if arr[i] == 0:

? ? ? ? ? ? if max_log_sum == float('-inf') and (result[0] > i + 1):

? ? ? ? ? ? ? ? result[0] = i + 1

? ? ? ? ? ? ? ? result[1] = i + 1

? ? ? ? ? ? continue

? ? ? ? ? ?

? ? ? ? # 當前區間的對數和

? ? ? ? current_log_sum = 0

? ? ? ? # 遍歷從i開始的所有可能的結束位置

? ? ? ? for j in range(i, n):

? ? ? ? ? ? # 如果當前數是0，結束當前內層循環

? ? ? ? ? ? if arr[j] == 0:

? ? ? ? ? ? ? ? break

? ? ? ? ? ?

? ? ? ? ? ? # 累加對數

? ? ? ? ? ? current_log_sum += log(arr[j])

? ? ? ? ? ?

? ? ? ? ? ? # 更新最大值和對應的區間

? ? ? ? ? ? if (current_log_sum > max_log_sum or

? ? ? ? ? ? ? ? (abs(current_log_sum - max_log_sum) < 1e-10 and i + 1 < result[0]) or

? ? ? ? ? ? ? ? (abs(current_log_sum - max_log_sum) < 1e-10 and i + 1 == result[0] and j + 1 < result[1])):

? ? ? ? ? ? ? ? max_log_sum = current_log_sum

? ? ? ? ? ? ? ? result[0] = i + 1

? ? ? ? ? ? ? ? result[1] = j + 1

? ?

? ? return result

?

if __name__ == "__main__":

? ? # Add your test cases here

? ? print(solution(5, [1, 2, 4, 0, 8]) == [1, 3])

? ? print(solution(7, [1, 2, 4, 8, 0, 256, 0]) == [6, 6])