Find the sub-array with the largest sum. [ALGORITHM PUZZLE Technical]
1,402.9K 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-
3 Question and 1 answer Riddle
One Mother and Daughter went to a market. .. The Shopkeeper asked the girl 3 questions. .. 1. WHAT DID ...Read More »You are a stand riddle
What goes around the world but stays in a corner?Read More »_ O _ A _ C_ Girls love it Boys use it riddle
_ O _ A _ C_ Complete this 7 letter word: Clue: 1. Girls love it 2. Boys use it ...Read More »Voting on how to distribute coins
100 coins are to be distributed among some number of persons, referred to by the labels A, B, C, D, ...Read More »5 sisters in a room puzzle
There are 5 sisters in a room: Ann is reading a book, Margaret is cooking, Kate is playing chess, Marie ...Read More »Mysterious Island
A man is surviving on an island along with his friend. They have been starving for four days for food. ...Read More »It is confusing
It could be confusing. It could be frustrating. It could be good. It could be funny. What is it ?Read More »Crossing Bridge Interview Puzzle
Four people are on this side of the bridge. the bridge will be destroyed by a bomb in 17 minutes. ...Read More »Who would you take?
If your overweight father-in-law, mother-in-law who looks like she’s about to die, and your wife approach you in your car ...Read More »Form A square
Solve the brain teaser by moving 3 sticks and form a square.Read More »Horror Film Dream Puzzle
Two brothers were watching a horror film on video late one night. One brother dozed off and dreamed that he ...Read More »Find out a relation and tell which number will suffice the pattern?
In the given figure, you can see that there are four circles numbered from 1 to 4. In the fourth ...Read More »Nobody in back
Look in my face, I am somebody; Look in my back, I am nobody. What am I ?Read More »Sherlock shoots the pilot riddle
Detective Sherlock entered a restaurant, he heard a voice coming from the kitchen of the restaurant “No Andrew, Don’t shoot“. ...Read More »All have me
When you have me not, you want me. But when you have me, you do not know. What am I?Read More »father and son question
if there are 1 son 1 father and 1 grandfather how many sons are thereRead More »Matching Pairs
Your sock drawer contains 24 white socks and 30 black socks. The lights in your room are off, so you ...Read More »Never rives Riddle
What is always on its way but never arrives?Read More »Cross the Gate
You need to complete the maze by entering from the entrance marked below in the figure near the yellow circle, ...Read More »Feed me and I live, give me drink and I die riddle
Feed me and I live, give me drink and I die. What am I?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