Thực hành tìm dãy con tổng lớn nhất

```python def maxSubarray(A, left, right): if left > right: return None, None, float('-inf') if left == right: return left, right, A[left] mid = (left + right) // 2 sumL, maxL, total = A[mid], mid, 0 for i in range(mid, left - 1, -1): total += A[i] if total > sumL: sumL, maxL = total, i sumR, maxR, total = A[mid + 1], mid + 1, 0 for j in range(mid + 1, right + 1): total += A[j] if total > sumR: sumR, maxR = total, j sumX = sumL + sumR leftL, rightL, bestL = maxSubarray(A, left, mid) leftR, rightR, bestR = maxSubarray(A, mid + 1, right) if bestL >= bestR and bestL >= sumX: return leftL, rightL, bestL if bestR >= bestL and bestR >= sumX: return leftR, rightR, bestR return maxL, maxR, sumX ``` sumL ban đầu bằng A[mid], sumR bằng A[mid+1], nên đoạn chéo không lấy phía rỗng để tránh số âm. Các biến total=0 chỉ làm tổng đang cộng, không phải đáp án mặc định. Hàm so kết quả tốt nhất bên trái, bên phải và qua giữa rồi trả (chỉ số đầu,chỉ số cuối,tổng). Cơ sở một phần tử trả chính giá trị ấy. Miền rỗng trả (None,None,−∞) như tín hiệu không có đoạn; không dùng các chỉ số None để cắt dãy.