Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Maximum Contiguous Subarray

Problem Statement
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur_sum = nums[0]
        max_sum = nums[0]
        for val in nums[1:]:
            if val < 0 and cur_sum < 0:
                cur_sum = max(cur_sum, val) 
            elif val >= 0 and cur_sum < 0:
                cur_sum = val
            else:
                cur_sum += val
                
            max_sum = max(max_sum, cur_sum) 
        return max_sum