Xin chào các bạn, hôm nay mình có bài tập này, thấy hay và cơ bản nên tôi sẽ chia sẻ các cách giải với các bạn

Bài tập này cũng cơ bản, nhưng mình muốn thêm vào để các bạn thấy tầm quan trọng của đọ phức tạp!

Đề bài: Cho trước 1 mảng độ lớn bằng n. Hãy tính toán tổng dãy con liên tiếp lớn nhất.

Đề bài này có thể sẽ đơn giản với 1 số người, nhưng việc thêm số âm vào khiến nó trở nên hay với thú vị hơn!

Từ giở, để dễ cho một số bạn chưa học về hàm thì sẽ có một số bài mình code luôn trong main nhé!

Hôm nay, mình sẽ trình bày 3 lời giải cho các bạn

Các ví dụ mình cho đều là số nguyên dương nhé, các bạn có thể thử với số âm =))))

LG1: Brute-force 💀💀💀

Thôi, khỏi trình bày nhiều nhé =))))

3 vòng lặp và chấm hết, ai cũng viết được

Code source:

Click me pls!

3 vòng lặp nên đơn giản, O(n^3)

Không tối ưu lắm nhỉ??

LG2: Giảm thiểu 1 vòng lặp(Thêm 1 brain cells là nghĩ ra ý mà =))))

Nhiều bạn đã lập trình quen có thể thấy 1 vòng lặp không cần thiết trong LG1, là tạo thêm 1 vòng lặp sau khi tạo ra đoạn dãy con!

Code source:

Click me pls!

Tuy nhiên, chưa đủ tối ưu với 1 vấn đề như thế này. Độ phức tạp 0(n^2)

LG3:

Để mình phân tích bài toán nhé

Đến 1 phần tử nào đó, các khả năng có thể là:

• Chỉ có duy nhất phần tử đó trong 1 dãy con

• Dãy con trước kết thúc ở k-1 và giờ thêm 1 phần tử nữa

Vì thế, dãy con ở k-1 cần là dãy con tổng lớn nhất thì tiếp tục tìm

Do đó, ta có lời giải tối ưu sau:

Click me pls!

Vì chỉ lặp 1 lần nên độ phức tạp O(n)!

Với lời giải 1, thời gian sẽ trên 10s với n>=10^4, lời giải 2 thì 10^6, lời giải 3 thì 10^7 vẫn chạy tốt

Qua đó, ta hiểu được tầm quan trọng của độ phức tạp!!!!

Mong các bạn học được nhiều điều từ bài đọc này! Tuy nhiên, nếu có lỗi gì hoặc chưa hiểu thì bạn hãy cứ nhắn nhé! Mình sẵn sàng trả lời!