Expedia Group Interview Question: Find the largest positive contiguous sum in a given array of ints(positive and negative ints) in linear time complexity.

Notifications

Expedia Group

Find the largest positive contiguous sum in a given array of ints(positive and negative ints) in linear time complexity.

Anonymous

Mar 4, 2012

Use dynamic programming!

Anonymous

Sep 8, 2013

This is Kadane’s Algorithm http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/ http://en.wikipedia.org/wiki/Kadane%27s_Algorithm