The Maximum Subarray

  • + 0 comments
    def maxSubarray(arr):
        max_val = max(arr)
        if max_val <= 0:
            return max_val, max_val
        max_sum = 0
        cur_sum = 0
        for i in range(len(arr)):
            if cur_sum + arr[i] < 0:
                cur_sum = 0
                continue
            cur_sum += arr[i]
            max_sum = max(max_sum, cur_sum)
        return max_sum, sum([i for i in arr if i > 0])