918. Maximum Sum Circular Subarray

Problem

Bài toán yêu càu tìm tổng lớn nhất của đoạn con liên tiếp (subarray) trong mảng số nguyên. Trong đó mảng là “vòng tròn” (circular), tức là có thể nối phần cuối với phần đàu để tạo thành đoạn liên tiếp

Approach

Có hai tường hợp chính

Trường hợp 1:

Đoạn con không “quấn vòng” túc là nằm hoàn toàn trong mảng như bình thường. Trường hợp này chính là bài toán "Maximum Subarray Sum" (Kadane's Algorithm).

Trường hợp 2

Đoạn con “quấn vòng”, tức là lấy một đoạn từ đầu mảng và một đoạn từ cuối mảng, bỏ qua đoạn giữa (liên tiếp). Khi đóm tổng lớn nhất sẽ là tổng cả mảng trừ đi tổng nhỏ nhất của một đoạn con liên tiếp (minimum subarray sum)

💡

Lưu ý

Nếu tất cả các phần tử đều âm, đáp án là phần tử lớn nhất (không nên lấy tổng cả mảng trừ đi tổng nhỏ nhất vì sẽ ra 0)

Các bước giải

Tìm tổng lớn nhất của một đoạn con liên tiếp (kadane algo)

Tìm tổng nhỏ nhất của một đoạn con liên tiếp (Kadane đảo đầu)

Tính tổng toàn mảng

Kết quả là max(đáp án 1, tổng toàn mảng - đáp án 2), trừ khi tất cả phần tử đều âm thì lấy đáp án 1

Solution

typescripttypescript

1function maxSubarraySumCircular(nums: number[]): number {
2    let curr_max =nums[0], global_max = nums[0];
3    let curr_min = nums[0], global_min = nums[0];
4    let total_sum = nums[0]
5    for(let i =1; i< nums.length; i++ ){
6	    const value =nums[i];
7	    curr_max = Math.max(curr_max + value, value)
8	    global_max = Math.max(global_max, curr_max)
9	    
10	    curr_min = Math.min(curr_min + value, value)
11	    global_min = Math.min(global_min, curr_min)
12	    
13	    total_sum += value
14    }
15    if(global_max < 0) reutrn global_max
16    return Math.max(global_max, total_sum - global_min)
17};

💡

total_sum - global_min (tổng toàn mảng trừ đi tổng nhỏ nhất của một đoạn con liên tiếp) chính là tổng lớn nhất khi chọn đoạn con “quấn vòng” trong mảng circular

Loading content...

1function maxSubarraySumCircular(nums: number[]): number { 2 let curr_max =nums[0], global_max = nums[0]; 3 let curr_min = nums[0], global_min = nums[0]; 4 let total_sum = nums[0] 5 for(let i =1; i< nums.length; i++ ){ 6 const value =nums[i]; 7 curr_max = Math.max(curr_max + value, value) 8 global_max = Math.max(global_max, curr_max) 9 10 curr_min = Math.min(curr_min + value, value) 11 global_min = Math.min(global_min, curr_min) 12 13 total_sum += value 14 } 15 if(global_max < 0) reutrn global_max 16 return Math.max(global_max, total_sum - global_min) 17};

918. Maximum Sum Circular Subarray

Related Posts

Related Posts

918. Maximum Sum Circular Subarray

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists