15 Jan 10 Question: You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum. Answer: This is an all-time favorite software interview question. The best way to solve this puzzle is to use Kadane’s algorithm which runs in O(n) time. The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values,
Read full article from Sub-Array with the Largest Sum » My Tech Interviews
No comments:
Post a Comment