資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學Python程式：查詢所有可能的有效路徑中的最大得分
假設我們有兩個陣列 nums1 和 nums2。有效路徑定義如下：
選擇 nums1 或 nums2 進行遍歷（從索引 0 開始）。
從左到右遍歷陣列。
現在，如果我們正在遍歷 nums1 和 nums2 中都存在的任何值，我們可以將路徑更改為另一個數組。這裡的得分是有效路徑中唯一值的總和。我們必須找到所有可能的有效路徑中我們可以獲得的最大得分。如果答案過大，則返回結果模 10^9+7。
因此，如果輸入類似於 nums1 = [3,5,6,9,11] nums2 = [5,7,9,10]，則輸出將為 35，因為：
從 nums1 開始的有效路徑為：[3,5,6,9,11]，[3,5,6,9,10]，[3,5,7,9,10]，[3,5,7,9,11]
從 nums2 開始的有效路徑為：[5,7,9,10]，[5,6,9,11]，[5,6,9,10]，[5,7,9,11]
所以最大值為 [3,5,7,9,11]。
為了解決這個問題，我們將遵循以下步驟：
M := nums1 的大小，N := nums2 的大小
sum1 := 0，sum2 := 0
i := 0，j := 0
res := 0
當 i < M 且 j < N 時，執行：
如果 nums1[i] < nums2[j]，則
sum1 := sum1 + nums1[i]
i := i + 1
否則，如果 nums1[i] > nums2[j]，則
sum2 := sum2 + nums2[j]
j := j + 1
否則，
res := res + sum1 和 (sum2 + nums1[i]) 中的最大值
i := i + 1
j := j + 1
sum1 := 0
sum2 := 0
當 i < M 時，執行：
sum1 := sum1 + nums1[i]
i := i + 1
當 j < N 時，執行：
sum2 := sum2 + nums2[j]
j := j + 1
返回 (res + sum1 和 sum2 中的最大值) mod 10^9+7
示例
讓我們看看下面的實現，以便更好地理解
def solve(nums1, nums2):
M, N = len(nums1), len(nums2)
sum1, sum2 = 0, 0
i, j = 0, 0
res = 0
while i < M and j < N:
if nums1[i] < nums2[j]:
sum1 += nums1[i]
i += 1
elif nums1[i] > nums2[j]:
sum2 += nums2[j]
j += 1
else:
res += max(sum1, sum2) + nums1[i]
i += 1
j += 1
sum1 = 0
sum2 = 0
while i < M:
sum1 += nums1[i]
i += 1
while j < N:
sum2 += nums2[j]
j += 1
return (res + max(sum1, sum2)) % 1000000007
nums1 = [3,5,6,9,11]
nums2 = [5,7,9,10]
print(solve(nums1, nums2))輸入
[3,5,6,9,11], [5,7,9,10]
輸出
35
508 次瀏覽
