Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Go] Tổng mảng con liên tiếp lớn nhất

    Cho dãy NNN số nguyên (có thể âm). Hãy tìm tổng lớn nhất của một mảng con liên tiếp khác rỗng bằng thuật toán Kadane: duyệt một lần bằng for, cập nhật cur = max(a[i], cur + a[i]) và best = max(best, cur).

    • Định dạng đầu vào:

      Dòng 1: NNN. Dòng 2: NNN số nguyên.

    • Ràng buộc đầu vào:

      1≤N≤1051 \le N \le 10^51≤N≤105, ∣ai∣≤109|a_i| \le 10^9∣ai​∣≤109.

    • Định dạng đầu ra:

      Tổng lớn nhất tìm được.

    Ví dụ:

    Đầu vào:

    9
-2 1 -3 4 -1 2 1 -5 4

    Đầu ra:

    6

    Giải thích:

    Mảng con [4,-1,2,1] có tổng = 6.

    Đang tải editor...