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).
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 subarrayl_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_creturn(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
import codewars_test as test from solution import max_sequence @test.describe("Max Sequence Tests") def test_group(): @test.it("Case 1") def test_case_1(): test.assert_equals(max_sequence([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]), 55) test.assert_equals(max_sequence([-22, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]), 55) test.assert_equals(max_sequence([0, 1, 2, 3, 4, 5, -6, 7, 8, 9, 10]), 43) test.assert_equals(max_sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 99, -1, 23, 43]), 164) test.assert_equals(max_sequence([2, 1, -5, 4, 3, 7, -6, -11, 12, 15, 20, -3, 5, -19]), 49) test.assert_equals(max_sequence([0] * 10), 0) test.assert_equals(max_sequence([-1] * 10), 0) test.assert_equals(max_sequence([1] * 10), 10)- import codewars_test as test
- from solution import max_sequence
- @test.describe("Max Sequence Tests")
- def test_group():
- @test.it("Case 1")
- def test_case_1():
test.assert_equals(max_sequence([0,1,2,3,4,5,6,7,8,9,10]), 55)test.assert_equals(max_sequence([-22,1,2,3,4,5,6,7,8,9,10]), 55)test.assert_equals(max_sequence([0,1,2,3,4,5,-6,7,8,9,10]), 43)test.assert_equals(max_sequence([0,0,0,0,0,0,0,0,0,99,-1, 23, 43]), 164)- test.assert_equals(max_sequence([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]), 55)
- test.assert_equals(max_sequence([-22, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]), 55)
- test.assert_equals(max_sequence([0, 1, 2, 3, 4, 5, -6, 7, 8, 9, 10]), 43)
- test.assert_equals(max_sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 99, -1, 23, 43]), 164)
- test.assert_equals(max_sequence([2, 1, -5, 4, 3, 7, -6, -11, 12, 15, 20, -3, 5, -19]), 49)
- test.assert_equals(max_sequence([0] * 10), 0)
- test.assert_equals(max_sequence([-1] * 10), 0)
- test.assert_equals(max_sequence([1] * 10), 10)