Marc Lester Tan

Another easy LC problem. Most solutions will probably have O(n^2) or worst but here’s an another solution which has an O(n) time complexity.

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        var sum = 0
        var max = Integer.MIN_VALUE
        
        nums.forEach { 
            sum = Math.max(it, sum + it)    
            max = Math.max(sum, max)
        }
        
        return max
    }
}

We loop through each item and we calculate the sum of all elements as we go through them. We then compare each element if it is higher than the accumulated sum. If it is, then use it as the new value of sum. Otherwise, keep on accumulating. Then, we take the highest sum so far which will be the output.

Runtime: 184 ms, faster than 70.00% of Kotlin online submissions for Maximum Subarray.
Memory Usage: 40.3 MB, less than 50.00% of Kotlin online submissions for Maximum Subarray.