Tìm dãy con liên tiếp không giảm có tổng lớn nhất

Lập trình Python

Để tìm dãy con liên tiếp không giảm có tổng lớn nhất, chúng ta có thể sử dụng thuật toán Dynamic Programming với độ phức tạp O(n). Cụ thể:

  1. Khởi tạo mảng dp với n phần tử, trong đó dp[i] là tổng lớn nhất của dãy con liên tiếp kết thúc tại phần tử thứ i.

  2. Khởi tạo giá trị dp[0] bằng giá trị của phần tử đầu tiên của mảng.

  3. Duyệt từ phần tử thứ hai đến phần tử cuối cùng của mảng:

    • Nếu phần tử thứ i lớn hơn hoặc bằng phần tử trước đó, tức là dãy con liên tiếp không giảm, ta cộng giá trị của phần tử i với dp[i-1] để tính tổng lớn nhất của dãy con liên tiếp kết thúc tại phần tử i.
    • Nếu phần tử thứ i nhỏ hơn phần tử trước đó, tức là dãy con liên tiếp bị đứt, ta gán dp[i] bằng giá trị của phần tử thứ i.
  4. Tìm giá trị lớn nhất trong mảng dp và trả về kết quả.

Dưới đây là mã nguồn Python minh họa cho thuật toán này:

def max_sum_subarray(arr):
    n = len(arr)
    dp = [0] * n
    dp[0] = arr[0]
    for i in range(1, n):
        if arr[i] >= arr[i-1]:
            dp[i] = dp[i-1] + arr[i]
        else:
            dp[i] = arr[i]
    return max(dp)

Chạy thử với một mảng đầu vào:

arr = [1, 2, 3, 2, 4, 5, 6, 1]
print(max_sum_subarray(arr)) # output: 18 (dãy con liên tiếp không giảm là [2, 4, 5, 6])

Với mảng đầu vào này, dãy con liên tiếp không giảm có tổng lớn nhất là [2, 4, 5, 6], với tổng bằng 18.

Chi tiết hơn, các bạn có thể tham khảo thuật toán quy hoạch động:

Để tìm dãy con liên tiếp không giảm có tổng lớn nhất trong một danh sách (list) các số nguyên, ta có thể sử dụng thuật toán quy hoạch động (dynamic programming) như sau:

def find_max_increasing_subsequence(lst):
    n = len(lst)
    # Khởi tạo mảng dp với giá trị mặc định là 1
    dp = [1] * n
    # Tìm dãy con tăng dài nhất bắt đầu từ các phần tử trong lst
    for i in range(1, n):
        for j in range(i):
            if lst[i] >= lst[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    # Tìm giá trị lớn nhất trong dp
    max_val = max(dp)
    # Tìm vị trí đầu tiên của dãy con tăng dài nhất
    start_idx = dp.index(max_val)
    # Tìm dãy con tăng dài nhất
    result = [lst[start_idx]]
    for i in range(start_idx+1, n):
        if lst[i] >= result[-1] and dp[i] == max_val-1:
            result.append(lst[i])
            max_val -= 1
    return result

# Test
lst = [2, 5, 1, 2, 4, 3]
print(find_max_increasing_subsequence(lst)) # output: [1, 2, 4]

Trong code trên, hàm find_max_increasing_subsequence() nhận đầu vào là một danh sách lst các số nguyên. Trong hàm này, ta sử dụng một mảng dp để lưu độ dài của dãy con tăng dài nhất bắt đầu từ mỗi phần tử của lst. Sau đó, ta tìm giá trị lớn nhất trong mảng dp, và từ đó tìm vị trí đầu tiên của dãy con tăng dài nhất. Cuối cùng, ta sử dụng mảng dp và vị trí đầu tiên để tìm ra dãy con tăng dài nhất có tổng lớn nhất.

Ở phần test, ta sử dụng danh sách lst có giá trị [2, 5, 1, 2, 4, 3] để kiểm tra hàm find_max_increasing_subsequence() có hoạt động đúng hay không. Kết quả trả về là dãy [1, 2, 4], có tổng là 7, đúng với kết quả mong đợi.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *