在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given a circular array C of integers represented by Here, a circular array means the end of the array connects to the beginning of the array. (Formally, Also, a subarray may only include each element of the fixed buffer Example 1: Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3
Example 2: Input: [5,-3,5]
Output: 10
Subarray [5,5] has maximum sum 5 + 5 = 10
Example 3: Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4
Example 4: Input: [3,-2,2,-3]
Output: 3
Subarray [3] and [3,-2,2] both have maximum sum 3
Example 5: Input: [-2,-3,-1]
Output: -1
Subarray [-1] has maximum sum -1
Note:
给定一个由整数数组 在此处,环形数组意味着数组的末端将会与开头相连呈环状。(形式上,当 此外,子数组最多只能包含固定缓冲区 示例 1: 输入:[1,-2,3,-2] 输出:3 解释:从子数组 [3] 得到最大和 3 示例 2: 输入:[5,-3,5] 输出:10 解释:从子数组 [5,5] 得到最大和 5 + 5 = 10 示例 3: 输入:[3,-1,2,-1] 输出:4 解释:从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4 示例 4: 输入:[3,-2,2,-3] 输出:3 解释:从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3 示例 5: 输入:[-2,-3,-1] 输出:-1 解释:从子数组 [-1] 得到最大和 -1 提示:
80 ms 1 class Solution { 2 func maxSubarraySumCircular(_ A: [Int]) -> Int { 3 if A == nil || A.count == 0 {return 0} 4 var preSumMin:Int = 0 5 var preSumMax:Int = 0 6 var preSum = 0 7 var sumMin = Int.max 8 var sumMax = Int.min 9 let count = A.count 10 for i in 0..<count 11 { 12 preSum += A[i] 13 sumMax = max(preSum - preSumMin, sumMax) 14 if i != (count - 1) 15 { 16 sumMin = min(preSum - preSumMax, sumMin) 17 } 18 preSumMin = min(preSumMin, preSum) 19 preSumMax = max(preSumMax, preSum) 20 } 21 return max(sumMax, preSum - sumMin) 22 } 23 } 300ms 1 class Solution { 2 func maxSubarraySumCircular(_ A: [Int]) -> Int { 3 4 var maxSum = A.max()! 5 6 var simpleA: [Int] = [] 7 simpleA.reserveCapacity(A.count) 8 var isPos = A.first! > 0 9 var sum = 0 10 for i in 0..<A.count { 11 if A[i] > 0 || A[i] < 0{ 12 if isPos == (A[i] > 0) { 13 sum += A[i] 14 } else { 15 simpleA.append(sum) 16 sum = A[i] 17 isPos = A[i] > 0 18 } 19 } 20 } 21 simpleA.append(sum) 22 23 let AA = simpleA + simpleA 24 25 iCycle: for i in 0..<simpleA.count { 26 if simpleA[i] < 0 { 27 continue iCycle 28 } 29 var sum = simpleA[i] 30 maxSum = max(sum, maxSum) 31 jCycle: for j in (i+1)..<(i+simpleA.count) { 32 sum += AA[j] 33 if sum < 0 { 34 continue iCycle 35 } 36 maxSum = max(sum, maxSum) 37 } 38 } 39 return maxSum 40 } 41 } 704ms 1 class Solution { 2 func maxSubarraySumCircular(_ A: [Int]) -> Int { 3 if A == nil || A.count == 0 {return 0} 4 var preSumMin:Int = 0 5 var preSumMax:Int = 0 6 var preSum = 0 7 var sumMin = Int.max 8 var sumMax = Int.min 9 let len = A.count 10 for i in 0..<len 11 { 12 preSum += A[i] 13 sumMax = max(preSum - preSumMin, sumMax) 14 if i != (len - 1) 15 { 16 sumMin = min(preSum - preSumMax, sumMin) 17 } 18 preSumMin = min(preSumMin, preSum) 19 preSumMax = max(preSumMax, preSum) 20 } 21 return max(sumMax, preSum - sumMin) 22 } 23 } 836ms 1 class Solution { 2 func maxSubarraySumCircular(_ A: [Int]) -> Int { 3 guard A.count > 0 else { 4 return 0 5 } 6 let s = A.reduce(0, +) 7 var M = A[0] 8 var m = A[0] 9 var lastM = A[0] 10 var lastm = A[0] 11 for i in 1 ..< A.count { 12 let a = A[i] 13 lastM = max(lastM+a, a) 14 lastm = min(lastm+a, a) 15 M = max(M, lastM) 16 m = min(m, lastm) 17 } 18 return M > 0 ? max(M, s-m) : M 19 } 20 } 948ms 1 class Solution { 2 func maxSubarraySumCircular(_ A: [Int]) -> Int { 3 var sum = 0 4 var curMax = 0 5 var curMin = 0 6 var maxSum = -30000 7 var minSum = 30000 8 for i in 0..<A.count { 9 sum += A[i] 10 curMax = max(curMax + A[i], A[i]) 11 maxSum = max(maxSum, curMax) 12 curMin = min(curMin + A[i], A[i]) 13 minSum = min(minSum, curMin) 14 } 15 return maxSum > 0 ? max(sum - minSum, maxSum) : maxSum 16 } 17 }
|
请发表评论