Chương trình tìm điểm tối đa từ tất cả đường đi hợp lệ trong Python

Cho hai mảng nums1, nums2. Đường đi hợp lệ: chọn nums1 hoặc nums2, duyệt trái sang phải. Nếu gặp giá trị có trong cả hai, có thể chuyển sang mảng kia. Điểm = tổng giá trị duy nhất trên đường đi. Tìm điểm tối đa, modulo 10^9+7.

Ví dụ: nums1 = [3,5,6,9,11], nums2 = [5,7,9,10], đầu ra = 35 (đường [3,5,7,9,11]).

Giải pháp

Two pointers duyệt song song, tích lũy tổng giữa các điểm chung:

• M, N := len(nums1), len(nums2)
• sum1, sum2 := 0, i, j := 0, res := 0
• Khi i < M và j < N:
  • Nếu nums1[i] < nums2[j]: sum1 += nums1[i]; i++
  • Nếu nums1[i] > nums2[j]: sum2 += nums2[j]; j++
  • Nếu bằng: res += max(sum1, sum2) + nums1[i]; i++; j++; sum1=0; sum2=0
• Cộng dồn phần còn lại của nums1 vào sum1, nums2 vào sum2
• Trả về (res + max(sum1, sum2)) % 1000000007

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

[3,5,6,9,11], [5,7,9,10]

Đầu ra

35