Given an int array, find the sequence of elements that has the largest sum

Question

Suresh · Accepted Answer

seems like simple sorting and then taking the last elements !!

if not, or 
MaxA; MaxB;

march thru elements and capture MaxA and MaxB. the sum of MaxA and MaxB will be the largest sum.

Anon · Answer

Wow what a really sick question..

1. Find the subarray of maximum sum starting from index 0.
2. Find the subarray of minimum sum starting from index 0 ending at the last index of maximum sum.
3. Max sum-Min sum= MAX

AbhijeetP · Answer

bool allNegatives = true;
            int largest = int.MinValue;

            for (int i = 0; i  array[i] ? largest : array[i];

                curMax = curMax + array[i];
                if (curMax > maxSoFar)
                {
                    maxSoFar = curMax;
                    maxEnd = i;
                    maxStart = curMaxStart;
                    allNegatives = false;
                }
                else if (curMax <= 0)
                {
                    curMax = 0;
                    curMaxStart = i + 1;
                }
            }

            if (allNegatives)
            {
                return largest;
            }
            return maxSoFar;
        }


Taken from 
http://www.technicalinterviewquestions.net/2009/01/largest-sum-sub-sequence-integer-array.html

Gee · Answer

Kadane's algorithm is the best one I think. Linear.

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas