Ad

Headline:

$O(n)$ time and $O(1)$ extra memory solution

Brief explanation:

Summation of every subarray tend to be time consuming if the length of the array increases, makes the trivial $O(n^2)$ solution struggle. But if we look closely at the underlying operations to calculate the summations, we find many repeated operations that we could avoid by storing them; more accurately, we can find and store the maximum possible sum starting at element i (defining as f(i)) and then find the maximum value among them.

Solution:

Notice that to calculate f(i), we have two options, either choose only element i, or attach element i to the next element, i.e., f(i) would be either a_i or a_i + f(i+1); either that is higher.
Based on this, we can go through the array backwards, find f(i) based on the previous element (f(i+1)), and finally find the maximum value of f(i) for all indices.
Furthermore, we can improve the extra memory needed by only storing the last calculated f; which enforces to also store the maximum f encountered (because we lose the ability to go through f later on).

Code
Diff
  • def max_sequence(arr):
        """Code to find maximum sum of subarray by checking the maximum possible sum for all starting elements
        """
        n = len(arr)
        sum_b = arr[-1]
        ans = max(0, sum_b)
        for i in range(n - 2, -1, -1):
            sum_b = max(arr[i], arr[i] + sum_b)
            ans = max(ans, sum_b)
        return ans
    
    • def max_sequence(arr):
    • # Code to find maximum sum of subarray
    • l_a = len(arr)
    • sum_b = sum(arr)
    • for i in range(l_a):
    • for k in range(l_a-i+1):
    • sum_c = sum(arr[k:k+i])
    • if sum_c > sum_b: sum_b = sum_c
    • return(sum_b)
    • """Code to find maximum sum of subarray by checking the maximum possible sum for all starting elements
    • """
    • n = len(arr)
    • sum_b = arr[-1]
    • ans = max(0, sum_b)
    • for i in range(n - 2, -1, -1):
    • sum_b = max(arr[i], arr[i] + sum_b)
    • ans = max(ans, sum_b)
    • return ans