Tìm mảng con có tổng lớn nhất trong mảng một chiều các số thực

[nudark1234 (Nguyen Luong)]

Cho em hỏi bài này làm sao ạ :((. Em cảm ơn.

[rogp10]

Về thuật toán Kadane

Mảng con của mảng A là mảng gồm các phần tử [A[i], A[i+1], …, A[j]], 1 <= i <= j <= |A|, kí hiệu A[i…j]. Quy ước A[1…|A|] = A (1-based array). Thuật toán Kadane là thuật toán dùng để tìm mảng con có tổng lớn nhất, và có thể mở rộng với điều kiện dãy có k phần tử trở lên hay mảng nhiều chiều. Thuật toán ban đầu được đặt ra cho ảnh bitmap (2D). Đây là giả mã của thuật toán 1D. -> A[1..N] : max_so_far = max_ending_here = A[1] : max(a, b) = if(a > b) a else b for i:=2 to N do max_ending_here :…