Given an array of integers (positive and negative) find the largest continuous sum.
If the array is all positive, then the result is simply the sum of all numbers. The negative numbers in the array will cause us to need to begin checking sequences.
The algorithm is, we start summing up the numbers and store in a current sum variable. After adding each element, we check whether the current sum is larger than maximum sum encountered so far. If it is, we update the maximum sum. As long as the current sum is positive, we keep adding the numbers. When the current sum becomes negative, we start with a new current sum. Because a negative current sum will only decrease the sum of a future sequence. Note that we don’t reset the current sum to 0 because the array can contain all negative integers. Then the result would be the largest negative number.
Let’s see the code:
def large_cont_sum(arr): # Check to see if array is length 0 if len(arr)==0: return 0 # Start the max and current sum at the first element max_sum=current_sum=arr[0] # For every element in array for num in arr[1:]: # Set current sum as the higher of the two current_sum=max(current_sum+num, num) # Set max as the higher between the currentSum and the current max max_sum=max(current_sum, max_sum) return max_sum
large_cont_sum([1,2,-1,3,4,10,10,-10,-1])
29
from nose.tools import assert_equal class LargeContTest(object): def test(self,sol): assert_equal(sol([1,2,-1,3,4,-1]),9) assert_equal(sol([1,2,-1,3,4,10,10,-10,-1]),29) assert_equal(sol([-1,1]),1) print('ALL TEST CASES PASSED') #Run Test t = LargeContTest() t.test(large_cont_sum)
ALL TEST CASES PASSED
Recommended: Understand Big-O Notation Complexity Of Algorithm
If you like my post please follow me to read my latest post on programming and technology.
Given an integer A. Compute and return the square root of A. If A is…
Given a zero-based permutation nums (0-indexed), build an array ans of the same length where…
A heap is a specialized tree-based data structure that satisfies the heap property. It is…
What is the Lowest Common Ancestor? In a tree, the lowest common ancestor (LCA) of…
A Binary Search Tree (BST) is a type of binary tree that satisfies the following…