Kadane's Algorithm

Đề bài

You are given an integer array arr[]. You need to find the maximum sum of a subarray (containing at least one element) in the array arr[].

Note : A subarray is a continuous part of an array.

Ví dụ

Input: arr[] = [2, 3, -8, 7, -1, 2, 3]
Output: 11
Explanation: The subarray [7, -1, 2, 3] has the largest sum 11.

Các bước thực hiện

Tôi có : arr = [-2, 3, -1, 2, -1]

Cách suy nghĩ đơn giản

• Thực hiện từ trái sang phải.
• Tại mỗi số, hãy tự hỏi:

👉 “Có nên tiếp tục cộng nó vào đoạn hiện tại, hay bỏ đoạn cũ đi và bắt đầu một đoạn mới từ số này?”

Bắt đầu

maxSum = -2
currentSum = -2

Xét khi gặp số arr[1] = 3:

• Nếu cộng với đoạn cũ: arr[0] + arr[1] = -2 + 3 = 1
• Nếu bắt đầu lại từ arr[1] = 3: 3 → Cái nào lớn hơn? 3 > 1 => Chọn bắt đầu lại tính từ vị trí arr[1] = 3;

Hãy xem mảng nhỏ hơn này, bạn thử nghĩ xem việc thêm -2 vào sum có làm tổng tăng nhiều hơn khi bắt đầu lại từ 3. Rõ ràng là bắt đầu lại từ 3 rồi, khi đó ta sẽ được tổng là 3, còn nếu thêm -2 thì tổng còn 1.

maxSum = 3
currentSum = 3, 

Xét tiếp khi gặp số -1:

• Nếu cộng tiếp: 3 + (-1) = 2
• Nếu bắt đầu mới: -1 → Chọn 2

maxSum = 3 (vì 3 > 2)
currentSum = 2, 

Xét tiếp khi gặp số 2:

• Nếu cộng tiếp: 2 + 2 = 4
• Nếu bắt đầu mới: 2 → Chọn 4

maxSum = 4
currentSum = 4

Khi gặp số -1:

• Nếu cộng tiếp: 4 + (-1) = 3
• Nếu bắt đầu mới: -1 → Chọn 3

maxSum = 4
currentSum = 3

Kết quả cuối cùng:

maxSum = 4
Đoạn con có tổng lớn nhất là [3, -1, 2].

Code

Ở đây tôi sử dụng C++ để giải quyết.

Nếu code theo những gì tôi đã giải thích bên trên thì nó sẽ như thế này

class Solution {
  public:
    int maxSubarraySum(vector<int> &arr) {
        int length = arr.size();
        int maxSum = arr[0];
        int currentSum = arr[0];
        
        for(int i = 1; i < length; i++) {
            currentSum = currentSum + arr[i];
            
            if(currentSum > arr[i]) { // không làm gì cả
                
            }
            else if(currentSum < arr[i]) {  // bắt đầu lại từ vị trí mới
                currentSum = arr[i];
            }
            
            
            if(currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        
        return maxSum;
    }
};

Đây là code rút gọn lại

class Solution {
  public:
    int maxSubarraySum(vector<int> &arr) {
        int length = arr.size();
        int maxSum = arr[0];
        int currentSum = arr[0];
        
        for(int i = 1; i < length; i++) {
            currentSum = currentSum + arr[i];
            if(currentSum < arr[i]) {
                currentSum = arr[i];
            }
            
            if(currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        
        return maxSum;
    }
};