53. Maximum Subarray
Tags:
Medium
Skills:
Kadane's algorithm
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Cách hoạt động của thuật toán Kadane
curr_sum (hoặc max_curr ): Tổng lớn nhất của dãy con kết thúc tại vị trí hiện tạicurr_sum là giá trị lớn nhất giữa phần tử hiện tại hoặc tổng curr_sum cộng phần tử hiện tạicurr_sum lớn hơn max_sum , cập nhật max_summax_sum là tổng lớn nhất của một dãy con liên tiếp trong mảngApproach thuật toán Kadane
Điều này nghĩa là nếu tổng hiện tại trở nên âm, ta bắt đầu một dãy mới từ nums[i]
Solution
1function maxSubArray(nums: number[]): number {
2 let current_sum = nums[0]
3 let max_sum = nums[0]
4 for(let i = 1; i < nums.lenght; i++) {
5 current_sum = Math.max(nums[i], current_sum + nums[i]);
6 max_sum = Math.max(max_sum, current_sum);
7 }
8
9 return max_sum
10};