c c++ leetcode

[LeetCode]各種Max subarray問題-1

Posted by John on 2019-09-16
Words 560 and Reading Time 2 Minutes
Viewed Times

我覺得我和這個題型特別有緣阿，之前實習面試還被問到，然後這兩週的week competition都有出到，下面就從最原始的問題開始，然後慢慢講解其他有的沒的變形題目。

第二篇看這裡：[LeetCode]各種Max subarray問題-2

LeetCode 53. Maximum Subarray

題意: 從array裡面找一個subarray，使得該subarray有最大的和。

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

1. 暴力掃過: 枚舉所有可能的區段，找出最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArray(vector& nums) {
        if(nums.empty()) return 0;

        int ans = nums[0];
        for(int i = 0 ; i < nums.size() ; i++){
            int temp = 0;
            for(int j = i ; j < nums.size() ; j++){
                temp = temp + nums[j];
                ans = max(ans, temp);
            }
        }
        return ans;
    }
};
};

2. kadane’s algo

DP方法，DP[i]記錄了在i-th當下的max subarray，DP[i]只有兩種可能:

  • DP[i] = arr[i]
  • DP[i] = DP[i-1] + arr[i]

最後掃過一次DP取得最大的值即可。實際上，可以一邊掃一邊存最大值，如此就不用另外開一個DP array。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector& nums) {
        if(nums.empty()) return 0;

        int temp_max = nums[0];
        int max_so_far = nums[0];

        for(int i = 1 ; i < nums.size() ; i++){
            temp_max = max(nums[i], temp_max+nums[i]);
            max_so_far = max(temp_max, max_so_far);
        }

        return max_so_far;
    }
};

LeetCode 918. Maximum Sum Circular Subarray

題意: 從array裡面找一個subarray，使得該subarray有最大的和，但這個array是一個circular array。

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

1. kadane’s algo

有兩種case:

  • max_sum_subarray在array中間，這時候直接用kadane’s algo
  • max_sum_subarray在array的頭跟尾，這時要換個想法，把問題轉成total_sum - min_sum_subarray(也是用kadane’s algo去計算)

答案在這兩個case取最大值即可 ，但要注意如果array全部都是負數，此時total_sum - min_sum_array = 0，會得到錯誤的結果，這個case要特別處理(直接回傳max_sum_subarray)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxSubarraySumCircular(vector& A) {
        int temp_max = A[0];
        int max_so_far = A[0];
        int temp_min = A[0];
        int min_so_far = A[0];
        int total_sum = A[0];

        for(int i = 1 ; i < A.size() ; i++){
            temp_max = max(A[i], temp_max + A[i]);
            max_so_far = max(max_so_far, temp_max);

            temp_min = min(A[i], temp_min + A[i]);
            min_so_far = min(min_so_far, temp_min);

            total_sum += A[i];
        }
        if(min_so_far == total_sum) return max_so_far;
        return max(max_so_far, total_sum-min_so_far);
    }
};
>