SeaCode

Appearance

Max Sum Contiguous Subarray ​

Problem Description ​

Find the contiguous subarray within an array, A of length N which has the largest sum.

Problem Constraints

1 <= N <= 10^6
-1000 <= A[i] <= 1000
1 <= N <= 10^6
-1000 <= A[i] <= 1000

Input Format

The first and the only argument contains an integer array, A.
The first and the only argument contains an integer array, A.

Output Format

Return an integer representing the maximum possible sum of the contiguous subarray.
Return an integer representing the maximum possible sum of the contiguous subarray.

Example Input

Input 1:
A = [1, 2, 3, 4, -10]
Input 2:
A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Input 1:
A = [1, 2, 3, 4, -10]
Input 2:
A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Example Output

Output 1:
10
Output 2:
6
Output 1:
10
Output 2:
6

Example Explanation

Explanation 1:
The subarray [1, 2, 3, 4] has the maximum possible sum of 10.
Explanation 2:
The subarray [4,-1,2,1] has the maximum possible sum of 6.
Explanation 1:
The subarray [1, 2, 3, 4] has the maximum possible sum of 10.
Explanation 2:
The subarray [4,-1,2,1] has the maximum possible sum of 6.

Solution ​

swift
import Foundation

class Solution {
	func maxSubArray(_ A: [Int]) -> Int {
        let len = A.count
        
        var max = Int.min
        var v = 0
        for i in 0..<len {
            v += A[i] 
            if v <= 0 {
                v = 0
            } else {
                if v > max {
                    max = v
                }
            }
        }
        if v == 0 {
            for i in 0..<len {
                if A[i] > max {
                    max = A[i]
                }
            }
        }
        
        // var max = Int.min
        // for i in 0..<len {
        //     var count = 0
        //     for j in 0..<(len-i) {
        //         count += A[i+j]
        //         if count > max {
        //             max = count
        //         }
        //     }

        // }
        return max
	}
}
import Foundation

class Solution {
	func maxSubArray(_ A: [Int]) -> Int {
        let len = A.count
        
        var max = Int.min
        var v = 0
        for i in 0..<len {
            v += A[i] 
            if v <= 0 {
                v = 0
            } else {
                if v > max {
                    max = v
                }
            }
        }
        if v == 0 {
            for i in 0..<len {
                if A[i] > max {
                    max = A[i]
                }
            }
        }
        
        // var max = Int.min
        // for i in 0..<len {
        //     var count = 0
        //     for j in 0..<(len-i) {
        //         count += A[i+j]
        //         if count > max {
        //             max = count
        //         }
        //     }

        // }
        return max
	}
}

References ​