# Find the sub-array with the largest sum. [ALGORITHM PUZZLE Technical]

1,484.3K 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-

### 50 red marbles and 50 blue marbles Puzzle

You have two jars, 50 red marbles and 50 blue marbles. A jar will be picked at random, and then ...Read More »### Mouth is so large

On my own, I am darkness, a black abyss. But, Life brings me light with its gentle kiss. I am ...Read More »### Mathematical Fraction

Using four sevens (7) and a one (1) create the number 100. Except for the five numerals, you can use ...Read More »### Eight letters long

I am eight letters long – “12345678” My 1234 is an atmospheric condition. My 34567 supports a plant. My 4567 ...Read More »### The Electrician

An electrician has two two-way switches (single-pole, double-throw), a light bulb, and a power source. How should he connect the ...Read More »### The more you work, the more I’ll eat riddle

The more you work, the more I’ll eat. You keep me full, I’ll keep you neat. What am I?Read More »### Earth and Heaven riddle

Scientists are trying to find out what is between earth and heaven. Can you find me?Read More »### Guess the Father’s name

Monday Tuesday and Wednesday are three sisters. What’s their father’s name?Read More »### EQUILATERAL TRIANGLE

There is an equilateral triangle and three bugs are sitting on the three corners of the triangle. Each of the ...Read More »### What killed him?

A man was going to bleach his socks because they had gotten muddy the day before. As he was pouring ...Read More »### Harry Potter Puzzle

Ponder upon a creature who exists in disguise Who deals in mysteries and has nothing to tell you except lies ...Read More »### Rocking Chair

What we call when we combine roller skates & a rocking chair.Read More »### Massage Parlour

Outside a massage parlour, there is a board that reads “I only massage those who do not massage themselves.” Reading ...Read More »### Keys that open no locks Riddle

I have keys that open no locks, I have space, but there is no room, You can enter, but you ...Read More »### How can you determine which one is magnetized and which is not?

You are in a room with two metal rods and no other metal. One of them is magnetized and the ...Read More »### What is the chance of flipping heads again?

You have three coins. One always comes up heads, one always comes up tails, and one is just a regular ...Read More »### Who was buried ?

Who was buried in Grant’s Tomb?Read More »### A boat full of people riddle

While walking across a bridge Andrew saw a boat full of people. Yet on the boat there wasn’t a single ...Read More »### Take before getting

What has taken before you can get it?Read More »### Turn the pyramid upside down by only moving 3 coins

In the picture, you can see a pyramid that is made of ten coins. By moving only 3 coins, can ...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