Find the sub-array with the largest sum. [ALGORITHM PUZZLE Technical]
1,601.4K Views
You are given an array with integers (both positive and negative) in any random order.
Find the sub-array with the largest sum.
Assuming neither the array nor sub-array can be empty, there are two possibilities.
- Either all values in the array are negative, in which case the sub-array with the largest sum is the 1-element sub-array containing the maximum value, or
- There are non-negative values in the array and the sub-array is bounded by negative value(s) and/or the maximum/minimum indexes.
The algorithm is to iterate through the array calculating the sum. Whenever the sum drops below zero, reset the sum to zero and reset the low index. Whenever the sum exceeds the maximum sum, record the new maximum and the sub-array indexes for the maximum.
Given an array a of size s:
msum = smallest negative integer mlow = -1 mhigh = -1 low = -1 sum = 0 for i = 0; i < s; i = i + 1 { if a[i] < 0 { if a[i] > msum { msum = a[i] mlow = mhigh = i } else { sum += a[i] if sum < 0 { sum = 0 low = -1 } } } else { if low == -1 { low = i } sum += a[i] if sum > msum { mlow = low msum = sum mhigh = i } } } // sub-array is a[mlow..mhigh] with a sum of msum
Your Answer
More puzzles to try-
Birthday gift mathematical puzzle
For my anniversary, I decided to surprise my wife. Since she is a voracious reader, I decided to collect a ...Read More »ABCD to DCBA riddle
ABCD × E = DCBA (Replace letters with digits and have the sum be true. A,B,C,D and E are all ...Read More »Becomes shorter when pulled
What is something that becomes shorter when pulled?Read More »Arrange 7\’s to 1
You need to arrange three 7 and mathematical symbols to form number 1?Read More »When he was a child riddle
In 1999, a 41-year-old doctor told his son that when a little boy he decided to be a doctor by ...Read More »Long & Short
Arnold Schwarzenegger’s is really long. Michael J. Fox’s is short. Daffy Duck’s isn’t human. Madonna doesn’t have one. What is ...Read More »How Come ??
Take 9 from 6, 10 from 9, 50 from 40 and leave 6. How Come ??Read More »Which room is safest for him?
A murderer is condemned to death. He has to choose between three rooms. The first is full of raging fires, ...Read More »Tactical Math Puzzle
Find the value of \”a\” by solving the maths equation in the picture below:Read More »Funny Good Puzzle
What does the rebus below mean? TEN BADTIONRead More »Whats going on riddle
A man leaves home, turns left, goes straight, turns left again, goes straight and turns left once more then returns ...Read More »Fake Murder Mystery
A crime was committed at baker street. Ibrahim Dakota who was shot in the stomach was the main suspect. Sherlock ...Read More »Who are the married couples?
Serge, Chris et Marc are married to Lise, Monique and Lily. Hints : 1) Serge loves golf but hates boating. 2) ...Read More »Clean bowled one day cricket match
Let’s say that a One Day International Cricket match is going on and every Batsman is getting clean bowled on ...Read More »Can Anna pull up if I pull up?
Anna can drive a Toyota, but not a Prius. She can marry Otto, but not Peter. She can borrow or ...Read More »Who is married
Three people are in a room. Ronni looks at Nile. Niile looks at Senthil. Ronni is married but Senthil is ...Read More »Which is correct to say, “The yolk of the egg is white” or “The yolk of the egg are white?”
Hint :Don’t focus on verbiageRead More »What does the following represent?
What does the following represent? N N N N N N N A A A A A A A C ...Read More »Each of us have different features riddle
Each of us have different features. Each of us are different creatures. One of us in glass is set Another ...Read More »Dies when his Suit Torn
A man was just doing his job when his suit was torn. Why did he die three minutes later?Read More »
Accenture Interview PuzzlesAdobe Interview PuzzlesAge RiddleAkbar Birbal PuzzlesAlgorithm PuzzlesAlphabet riddleAmazon Interview PuzzlesAnalytical MathematicsAptitude PuzzleBank PuzzlesBetting PuzzlesBrain TeasersCalendar PuzzlesCards PuzzlesChess Board PuzzleChess PuzzlesChristmas Puzzlecipher PuzzleCivil Services PuzzleClock time puzzleCognizant Interview PuzzlesCoins PuzzleComputational PuzzleconundrumCoronavirus PuzzleCoupondunia Interview PuzzleCritical Thinking Puzzledata analyticsData Structure Interview QuestionsDecode PuzzleDetective PuzzlesDice PuzzleDictionary Riddlesdifficult riddleEasy Math puzzlesEasy puzzlesEinstein puzzleEnglish RiddleFamily Tree Puzzlefamous puzzleFill in the blanks riddlesFinding Killer RiddlesFlipkart interview puzzlesFunny RiddlesGeneral KnowledgeGeographical PuzzleGoogle Code Jam 2014Google Interview PuzzlesGRE PuzzleHard Puzzle