Kadane's algorithm

昨天練習的題目是 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