連続した値の組み合わせの和で最大のものを出力する
input
-10, 2, 3, -2, 0, 5, -15 2,3,-2,-1,10
output
8 12
Kadane's algorithmというのが使えるらしい
ただし、すべての値がマイナスだと結果が0になってしまう(空配列)
その場合は、処理中に一番大きな値も保持しておいてそれを返す
参考 : Maximum subarray problem - Wikipedia, the free encyclopedia
連続した値の組み合わせの和で最大のものを出力する
input
-10, 2, 3, -2, 0, 5, -15 2,3,-2,-1,10
output
8 12
Kadane's algorithmというのが使えるらしい
ただし、すべての値がマイナスだと結果が0になってしまう(空配列)
その場合は、処理中に一番大きな値も保持しておいてそれを返す
参考 : Maximum subarray problem - Wikipedia, the free encyclopedia