-
Notifications
You must be signed in to change notification settings - Fork 0
/
15MaximumSumCircularSubarray.swift
44 lines (40 loc) · 1.07 KB
/
15MaximumSumCircularSubarray.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//
// ViewController.swift
// StockPrices
//
// Created by thailinh on 5/16/20.
// Copyright © 2020 thailinh. All rights reserved.
//
import UIKit
class Solution {
func findMaxSumSubArray(list : [Int]) -> Int{
var maxSumTemp = 0
var maxSum = Int.min
for item in list{
maxSumTemp += item
if maxSum < maxSumTemp{
maxSum = maxSumTemp
}
maxSumTemp = max(maxSumTemp,0)
}
return maxSum
}
func maxSubarraySumCircular(_ A: [Int]) -> Int {
let maxOfInitialList = findMaxSumSubArray(list: A)
var total = 0
for item in A{
total += item
}
var listA2 = [Int]()
listA2.append(contentsOf: A)
for index in 0..<listA2.count{
listA2[index] = A[index] * -1
}
let maxTemp = findMaxSumSubArray(list: listA2)
let flipSum = total + maxTemp
if flipSum > maxOfInitialList && flipSum != 0 {
return flipSum
}
return maxOfInitialList
}
}