Đoạn Con Tổng Lớn NhấtMaximum Subarray

1function maxSubArray(nums: number[]): number {
2  let curr = nums[0]  // tổng đoạn tốt nhất KẾT THÚC tại i
3  let best = nums[0]
4  for (let i = 1; i < nums.length; i++) {
5    curr = Math.max(nums[i], curr + nums[i])
6    best = Math.max(best, curr)
7  }
8  return best
9}

1. 1

   Hình dung nums = [-2, 1, -3, 4, -1, 2].

   Khởi tạo curr = best = nums[0] = −2.

   i:0curr:-2best:-2
2. 2

   i=1 (1): curr = max(1, −2+1=−1) = 1 (bắt đầu lại tốt hơn nối). best = max(−2, 1) = 1.

   i:1curr:1best:1
3. 3

   i=2 (−3): curr = max(−3, 1−3=−2) = −2. best vẫn 1. i=3 (4): curr = max(4, −2+4=2) = 4 → bỏ tiền tố âm, bắt đầu lại. best = 4.

   i:3curr:4best:4
4. 4

   i=4 (−1): curr = max(−1, 4−1=3) = 3. i=5 (2): curr = max(2, 3+2=5) = 5. best = max(4, 5) = 5.

   Trả về 5 (đoạn [4,−1,2]).

   i:5curr:5best:5result:5