Como obter a sub-matriz de soma máxima apenas para sub-matrizes não-negativas

Uma implementação muito direta:

public static int[] LargestLongestFirst(int[] source)
{
int curSum = 0, curStart = 0, curLength = 0,
maxSum = 0, maxSart = 0, maxLength = 0; for (int index = 0; index < source.length; index++)
{
if (source[index] < 0)
{
if ((curSum > maxSum) || ((curSum == maxSum) && (curLength > maxLength)))
{
maxSum = curSum;
maxSart = curStart;
maxLength = curLength;
}
curStart = index + 1;
curSum = curLength = 0;
}
else
{
curSum += source[index];
++curLength;
}
}
if ((curSum > maxSum) || ((curSum == maxSum) && (curLength > maxLength)))
{
maxSum = curSum;
maxSart = curStart;
maxLength = curLength;
}
int[] result = new int[maxLength];
System.arraycopy(source, maxSart, result, 0, maxLength);
return result;
}

public static int[] LargestLongestFirst(int[] source)
{
int curSum = 0, curStart = 0, curLength = 0,
maxSum = 0, maxSart = 0, maxLength = 0; for (int index = 0; index < source.length; index++)
{
if (source[index] < 0)
{
if ((curSum > maxSum) || ((curSum == maxSum) && (curLength > maxLength)))
{
maxSum = curSum;
maxSart = curStart;
maxLength = curLength;
}
curStart = index + 1;
curSum = curLength = 0;
}
else
{
curSum += source[index];
++curLength;
}
}
if ((curSum > maxSum) || ((curSum == maxSum) && (curLength > maxLength)))
{
maxSum = curSum;
maxSart = curStart;
maxLength = curLength;
}
int[] result = new int[maxLength];
System.arraycopy(source, maxSart, result, 0, maxLength);
return result;
}

Observe a parte duplicada após o loop. Essa é uma situação agradável em que um lambda poderia ter reduzido o código duplicado. Embora o escopo específico de Java com lambdas não permita, na verdade, referir-se a conter vars locais de escopo, a menos que sejam finais. Outro lugar onde o C # está um pouco à frente do Java. Por exemplo, o mesmo algoritmo acima pode ser escrito assim em C #:

public static int[] LargestLongestFirst(int[] source)
{
int curSum = 0, curStart = 0, curLength = 0, maxSum = 0,
maxSart = 0, maxLength = 0;
Action check = () => {
if ((curSum > maxSum) || ((curSum == maxSum) && (curLength > maxLength))) {
maxSum = curSum;
maxSart = curStart;
maxLength = curLength;
}
};
for (int index = 0; index < source.Length; index++) {
if (source[index] < 0) {
check();
curStart = index + 1;
curSum = curLength = 0;
} else {
curSum += source[index];
++curLength;
}
}
check();
var result = new int[maxLength];
Array.Copy(source, maxSart, result, 0, maxLength);
return result;
}

Você pode usar uma abordagem de programação dinâmica, na qual você mantém duas variáveis ​​maxsum e soma atual, ambas inicializadas com zero. Agora, comece a percorrer o loop.
Adicione o elemento atual às variáveis ​​de soma atual e agora verifique se a soma atual é menor que zero, faça a soma atual igual a zero e vá para o próximo elemento e, se não for negativo, compare-o com maxsum se max soma for menor que atualize a soma máxima e vá para o próximo elemento.

Editar: a resposta abaixo é para uma versão anterior da pergunta. Eu acho que não faz sentido resolver todo o dever de casa de quem pede. Pense por si mesmo!

O loop externo tenta todas as posições iniciais do subarray. Isso é bom. Mas o loop interno sempre é executado no final da matriz antes de verificar se você tem um novo máximo.
Então mova o ‘max’ para o loop interno para tentar todas as posições finais do subarray.