0918_maximum-sum-circular-subarray

command

v0.0.0-...-60194e6 Latest Latest Go to latest Published: Dec 9, 2020 License: Unlicense Imports: 0 Imported by: 0

Details

第一反应是dp.

在不考虑循环的情况: 计算dp[i]对于A[0, i)的max sum suffix.

dp[i] = max{ dp[i-1], 0 } + A[i-1]

max(dp)即答案

在考虑循环的情况下, 需要记录所得dp[len(A)]suffix的起始start.

计算A[0, lenA)的max sum preffixmaxSumPreffix.

dp[len(A)]所记录的start会在计算过程中被右移.

dp数组可以简化, 因为我们只用到了上次一的值.

There is no documentation for this package.