昨天練習的題目是 3381. Maximum Subarray Sum With Length Divisible by K，題目的最佳解是利用 Kadane's algorithm，我覺得比較容易理解的方式是先計算前面 k-1 個 kSum 之後，再往後面用 Kadane's algorithm 來解。
如果是寫 C++ 是這樣：
class Solution {
public:
long long maxSubarraySum(vector< int>& nums, int k) {
const int n = nums.size();
vector< long long> kSum(k, 0);
long long maxSum = numeric_limits< long long>::min(), prefixSum = 0;
for (int i = 0; i < k - 1; ++i) {
prefixSum += nums[i];
kSum[i] = prefixSum;
}
for (int i = k - 1; i < n; ++i) {
prefixSum += nums[i];
int r = i % k;
maxSum = max(maxSum, prefixSum - kSum[r]);
kSum[r] = min(kSum[r], prefixSum);
}
return maxSum;
}
};
寫 Python3 是這樣：
class Solution:
def maxSubarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
kSum = [0] * k
prefixSum = 0
maxSum = float("-inf")
for i in range(k - 1):
prefixSum += nums[i]
kSum[i] = prefixSum
for i in range(k - 1, n):
prefixSum += nums[i]
r = i % k
maxSum = max(maxSum, prefixSum - kSum[r])
kSum[r] = min(kSum[r], prefixSum)
return maxSum
寫 Go 是這樣，這邊要注意即便是使用 math.MinInt64 還是要用 int64() 明確轉型，不然預設會用 int 然後就會跟後面的 int64 衝突。
func maxSubarraySum(nums []int, k int) int64 {
n := len(nums)
kSum := make([]int64, k)
prefixSum, maxSum := int64(0), int64(math.MinInt64)
for i := range n {
prefixSum += int64(nums[i])
if i < k-1 {
kSum[i] = prefixSum
continue
}
r := i % k
maxSum = max(maxSum, prefixSum-kSum[r])
kSum[r] = min(kSum[r], prefixSum)
}
return maxSum
}
寫 Rust 是這樣，沒什麼特別要注意的地方，反正寫錯時編譯器會提醒你該如何修正。 :-P
impl Solution {
pub fn max_subarray_sum(nums: Vec< i32>, k: i32) -> i64 {
let k = k as usize;
let n = nums.len();
let mut kSum = vec![0i64; k];
let mut prefixSum = 0i64;
let mut maxSum = i64::MIN;
for i in 0..(k-1) {
prefixSum += nums[i] as i64;
kSum[i] = prefixSum;
}
for i in (k-1)..n {
prefixSum += nums[i] as i64;
let r = i % k;
maxSum = maxSum.max(prefixSum - kSum[r]);
kSum[r] = kSum[r].min(prefixSum);
}
maxSum
}
}
不曉得為何，寫 Rust 有最愉快的感覺。 :-P
