# 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.

SherlockHolmes Expert Asked on 22nd October 2015 in

Assuming neither the array nor sub-array can be empty, there are two possibilities.

1. 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
2. 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
```

dougbell Genius Answered on 24th October 2015.

• ## 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 »

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 »