#LeetCode:918. Maximum Sum Circular Subarray

灆洢 2020-05-16 01:45:51

此題要找出,在陣列可循環的時候,其連續的子陣列中總和最大是多少。

提示的部分有提到這題在不循環的時候可以使用 Kadane's algorithm,即從頭開始做加總,如果其中加到總和變成負的,則就不管前面的總和,從該元素重新計算總和,最後找出每一段總和中最大的即是不循環時的答案。

而循環的部分,可以想成是找出不選某段連續的子陣列後,可以造成的最大總和是多少。透過這個想法,就變成在使用 Kadane's algorithm 的時候,是從陣列總和往下減一段連續的子陣列讓總和變大,如果減的過程出現的結果比陣列總和還低,則就不管前面不選哪些元素,從該元素重新從陣列總和繼續往下減,最後找出每一段減完最大的即是必定循環時的答案。

最後就將上述找到的兩個解答再取最大即是本題的答案。

P.S. 在做不選的部分的時候,記得不能不選整個陣列,一定至少要選一個元素。

Kotlin(312ms)

/*******************************************************
 * LeetCode 918. Maximum Sum Circular Subarray         *
 * Author: Maplewing [at] knightzone.studio            *
 * Version: 2020/05/16                                 *
 *******************************************************/
class Solution {
    fun maxSubarraySumCircular(A: IntArray): Int {
        var maxSum = Int.MIN_VALUE
        var currentSum = 0

        // Case 1: Take a subarray
        for (num in A) {
            currentSum = if (currentSum < 0) {
                num
            } else {
                currentSum + num
            }

            maxSum = Math.max(maxSum, currentSum)
        }

        // Case 2: Not take a subarray
        val totalSum = A.sum()
        var notTakeCount = 0
        currentSum = totalSum
        for (num in A) {
            if (currentSum < totalSum) {
                notTakeCount = 0
                currentSum = totalSum - num
            } else {
                ++notTakeCount
                currentSum -= num
            }

            if (notTakeCount < A.size) {
                maxSum = Math.max(maxSum, currentSum)
            }
        }

        return maxSum
    }
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料