Problem #4: MaxSub Array

Status: Resolved
Bài toán tìm mảng con có tổng lớn nhất trong mảng có n phần tử.

Ví dụ:

[-1, 5, -4, 8, -10] => chuỗi con lớn nhất [5,-4,8]

[4, -5, 1, 7, -12, 8, -2, 15, -119, 10, 3] => chuỗi con lớn nhất [8,-2,15]

Yêu cầu độ phức tạp là O(n)

Let's code!

Bài toán này khá là kinh điển rồi, khi tìm hiểu về cách giải nhiều người hay đề cập đến giải thuật Kadane để tìm tổng lớn nhất liên tục của các phần tử trong mảng:

Tuy nhiên để lấy được mảng con thì mình sẽ tạo 1 mảng để truy vết như sau:

  • dailycoding
  • algorithm
  • programming
Loading
Đăng nhập để bình luận