Max Sum Contiguous Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example:

Given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

For this problem, return the maximum sum.

My Solutions:

import sys


def maxSubArray(A):
    size = len(A)
    max_sum = max(A[0], -sys.maxsize - 1)
    for i in range(size):
        result = A[i]
        for j in range(i + 1, size):
            if i == j - 1:
                max_sum = max(max_sum, A[j])
                result += A[j]
                max_sum = max(max_sum, result)

            else:
                result += A[j]
                max_sum = max(max_sum, result)

    return max_sum


A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

print(maxSubArray(A))

It was a little bit hard to solve this problem...

First of all, I confused this problem. I thought I had to return list type, so I tried to check maximum sum index.

However, return type is int, so you don't waste of your time to find index.

Secondly, My time complexity is O(N^2). But, I realized that the best time complexity is O(N) after submitting my code.

I could not solve this problem on my own, so I search the google and find it.

Good solutions:

def maxSubArray(A):
    size = len(A)
    max_so_far = A[0]
    curr_max = A[0]

    for i in range(1, size):
        curr_max = max(A[i], curr_max + A[i])
        max_so_far = max(max_so_far, curr_max)

    return max_so_far

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

Read above url aritlce.