Problem
Given an array of elements, find the maximum possible sum of a
- Contiguous subarray
- Non-contiguous (not necessarily contiguous) subarray.
Empty subarrays/subsequences should not be considered.
Input Format
First line of the input has an integer . cases follow.
Each test case begins with an integer . In the next line, integers follow representing the elements of array .
Constraints:
The subarray and subsequences you consider should have at least one element.
Output Format
Two, space separated, integers denoting the maximum contiguous and non-contiguous subarray. At least one integer should be selected and put into the subarrays (this may be required in cases where all elements are negative).
Sample Input
2
4
1 2 3 4
6
2 -1 2 3 4 -5
Sample Output
10 10
10 11
Explanation
In the first case:
The max sum for both contiguous and non-contiguous elements is the sum of ALL the elements (as they are all positive).
In the second case:
[2 -1 2 3 4] –> This forms the contiguous sub-array with the maximum sum.
For the max sum of a not-necessarily-contiguous group of elements, simply add all the positive elements.
Solution
func maxSubarray(array : [Int]) -> Int{
var max_ending_here = array[0]
var max_so_far = array[0]
//2 -1 2 3 4 -5
for i in 1..<array.count {
let x = array[i]
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
}
return max_so_far
}
// read the integer n
var numberOfTestCases = Int(readLine()!)!
for testCase in 0..<numberOfTestCases {
var numberOfElements = Int(readLine()!)!
//store input into array
var arr : [Int] = readLine()!.characters.split(" ").map{Int(String($0))!}
//find sum of Contiguous subarray. Using Kadane's algorithm in Swift
let sum1 = maxSubarray(arr)
//find sum of Non-Contiguous subarray. Just sum up all positive values
var sum2 = 0
for index in 0..<numberOfElements {
if (arr[index] > 0) {sum2 = sum2 + arr[index]}
}
//if sum2 is still 0 it means all elements are negative or 0's, so we will find a biggest
if (sum2 == 0){
sum2 = arr[0]
for index in 1..<numberOfElements {
if (arr[index] > sum2) {sum2 = arr[index]}
}
}
print("\(sum1) \(sum2)")
}