Pergunta de entrevista da empresa Microsoft

You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum.