# Problem

Đây là một bài toán khá phổ biến ở các trang về thuật toán, xếp loại medium, nó là cơ sở của nhiều bài được các công ty công nghệ sử dụng cho interview.
Đề bài:
Cho một mảng gồm N phần tử arr = [1, -2, 3, 4]. Tìm tổng lớn nhất có thể tạo ra từ các subarray của mảng arr ban đầu.

Solution

• Brute force solution
  Đây là giải thuật toán đơn giản nhất đề cài đặt cho bài toán nhưng độ phức tạp khá lớn không thể chạy được các input với size lớn khi test performance trong các bài interview.

findMaxSubArray(arr):
    maxSum = 0
    for i from 0 to arr.length - 1 do
        for j from i to arr.length -1 do
            maxSum =max(maxSum, sum(arr[i->j]))
    return maxSum

Với giải thuật như trên thì độ phức tạp rơi vào lớp O(n^3)

• Giải thuật kadane
  Giải thuật này có ý tưởng như sau với mỗi arr[i] thì ta sẽ xem xét arr[i] này sẽ từ nó tạo ra một array mới để kiểm tra hay là gắng nó vào subarray trước đó. Và quyết định sẽ phụ thuộc vào arr[i] có làm tăng sum của subarray đang xây dựng ngay trước nó hay không. Nếu arr[i] làm giảm giá trị của subarray trước đó thì ta sẽ xét đến array mới arr[i] là giá trị đâù tiên và kiểm tra sum của subarray mới có lớn hơn max sum lớn nhất đang lưu trữ hiện tại hay không và cập nhật lại max sum. Trong tình huống, arr[i] trờ thành đuôi của subarray đang dựng trước đó thì kiểm tra sum của subarray mà arr[i] tham gia vào so với max sum để cập nhật max sum.

findMaxSubArray(arr):
    globalSum = arr[0]//max sum
    curSum = arr[0]
    for i from 1 to arr.length -1 do
        curSum = max(curSum + arr[i], arr[i])
        globalSum = max(globalSum, curSum)
    return globalSum

Và độ phức tạp về thơi gian của giải thuật này là o(n)