4가지 풀이 법

완전 탐색 O(N^3)

for i in 0..<array.count {
	for j in i..<array.count {
		var temp
		for k in i...j {
				temp == array[k]
		}
		if temp > max {
			max = temp
			ans_i = i
			ans_j = j
		}
	}
}

완전 탐색 with PrefixSum O(N^2)

var prefix = Array(repeating: 0 , count: array.count)
var sum = 0
for i in 0..<prefix.count {
		sum += array[i]
		prefix[i] = sum
}

for i in 0..<array.count {
		for j in i..<array.count {
				var temp = 0
				if i == j { temp = array[i] }
				temp = prefix[j] - prefix[i - 1]
				if temp > max {
						max = temp
						ans_i = i
						ans_j = j
				}
		}

}

DP

var dp = Array(repeating: 0, count: n)
//dp[k]  : a[k]로 끝나는 최대 구간 합
dp[0] = a[0]
var ans = Int.min
for k in 1..<a.count {
		dp[k] = max(dp[k-1] + a[k], a[k])
		ans = max(ans , dp[k])
}
return ans