duckingmomoMới đọc được một ý tưởng khá hay về vấn đề này, tuy độ chính xác mình chưa kiểm chứng nhưng có vẻ đúng về lý thuyết:
B1: Tính tổng n phần tử của mảng. Kiểm tra tổng. Nếu tổng này dương, đưa output ra. Ngược lại, lên bước 2.
B2: Trừ khỏi tổng giá trị của phần tử cuối. Kiểm tra tổng. Nếu tổng còn lại dương, đưa output. Nếu không, đến bước 3.
B3: Làm lại bước 2 nhưng trừ khỏi tổng phần tử đầu thay vì cuối. Nếu tổng còn lại dương, đưa output. Nếu không, sang bước 4.
B4: Vẫn làm lại bước 2 nhưng lần này trừ cả đầu và cuối. Nếu tổng còn lại dương, đưa output ra. Nếu không, sang bước 5.
B5: Lặp lại lần lượt bước 2,3,4 cho đến khi tìm thấy tổng dương hoặc đến khi mảng còn lại ta đang xét không có phần tử nào.
Độ phức tạp ước tính (3/2).N
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
