Problema do Segmento de Soma Máxima

Escreva um programa que resolva o seguinte problema: dada uma seqüência de n números inteiros
, encontre índices l,r, com l <= r, tais que a soma

seja máxima. Por exemplo, dada a seqüência

1, -3, 6, -4, 2, -5, 1, 8, -4, 2, 3, -1, 2, -3, 1, 3, -5, 3 , -3, 4,

seu programa deve devolver os índices 6 e 15, pois o segmento

1, 8, -4, 2, 3, -1, 2, -3, 1, 3

tem soma igual a 1+8-4+2+3-1+2-3+1+3 = 12, que é máxima.
[Hmmmmm, é máxima mesmo?!?]