我覺得我和這個題型特別有緣阿，之前實習面試還被問到，然後這兩週的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);
}
};
|