Find the sub-array with the largest sum. [ALGORITHM PUZZLE Technical]
1,308.5K 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-
What is the color of the sole marble left in the bag ?
There is a bag which have 21 blue balls and 23 red balls. You also have 22 red balls outside ...Read More »Find the Goldfish
Find the Goldfish below the given Image.Read More »Round the earth riddle
The circumference of the Earth is approximately 40,000 kilometers, and someone has just made a metal band that circles the ...Read More »Chocolates on demnand Riddle
John brings 1000 chocolates for his sister and ten boxes as well. He asks his sister to place the chocolates ...Read More »A doctor was to operate a person as there was riddle
A ______ doctor was ________ to operate a person as there was ______ One word fills all 3 blanks. What ...Read More »Smiling in Sadness
There were three women in all the swimming costumes! One was happy and the other two were sad! The happy ...Read More »lady, Book and a man on the counter puzzle
A woman goes to the counter and puts a book before the man there. The man says that the price ...Read More »BOXES WITH MARBLES
You have three boxes full of marbles. There are stickers saying “white” “red” “red and white” on them indicating what ...Read More »Number Coding
In a certain code, MONKEY is written as 83. How is TIGER written in that code?Read More »Shoe Riddle
Who sleeps with their shoes on?Read More »Chess Game
John and Jacob play 5 games of chess. Both John and Jacob win the exact same number of games. There ...Read More »South West Direction
If we change the South-East direction into North and North-East into West and all others similarly. Can you find out ...Read More »Full Name Guessing Riddle
???? Do you know the full form of these words❓❓ ?? NEWS PAPER – ?? CHESS ?? COLD ?? JOKE ...Read More »Pictures to Identify
Identify the ten differences between the two given pictures below.Read More »Detective gone missing riddle
A detective who was mere days from cracking an international smuggling ring has suddenly gone missing. While inspecting his last-known ...Read More »Can you find out the result of the individual games?
Aaron, Brad, Christopher, Danny and Elvis decided to play a game of tiddly winks. In this game they decided that ...Read More »How many holes are there in the T-Shirt puzzle
How many holes are there in the T-Shirt whatsapp PuzzleRead More »Coin rotating riddle
How many times does a coin rotate in rolling completely about another coin, of the same size, without slipping, whilst ...Read More »The electrician problem
You’re an electrician working at a mountain. There are N wires running from one side of the mountain to the ...Read More »Loin and Unicorn in the Forest of Forgetfulness puzzle
One day Alice meets the Lion and the Unicorn in the Forest of Forgetfulness. She knows that the Lion lies ...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