【codewars】Maximum subarray sum【最大サブシーケンスの和を求める】
2377 ワード
テーマ
The maximsum subsequence in array or list of integers:
Empty list is consided to have zergreatest sum.Note that the empty list or array is also a valid sublist/subarray.
考え方
最初はこの問題を手に入れましたが、思いもよらず、暴力的に解決する方法しか思いつかなかったです.でも、自分でも一番いい考えが思いつかなかったので、ソロライブに行って他の人を見るしかなかったです.他の人のコードを見ましたが、考えはまだ分かりませんでした.ネットで他の人の説明の招待状を探して、参考にしました.
ポイントは、一段のサブアレイarr[i]-arr[j]の和がマイナスの場合、この配列の次の要素arr[j+1]を終点とする最大のサブアレイの和が必ずarr[j+1]そのものです.
2つの補助変数を使用すると、
コード実現(JS)https://www.jianshu.com/p/4edab8dbea9f 結びのことば
やはり多く問題をこすって、自分のいくつか思惟の習慣を維持するようにしましょう、頑張って!
The maximsum subsequence in array or list of integers:
maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
// should be 6: [4, -1, 2, 1]
Easy case is when the list is made up of only positive numbers and the maximsum is the sum of the whole array.If the list is made up of only negative numbers,return 0 instead.Empty list is consided to have zergreatest sum.Note that the empty list or array is also a valid sublist/subarray.
考え方
最初はこの問題を手に入れましたが、思いもよらず、暴力的に解決する方法しか思いつかなかったです.でも、自分でも一番いい考えが思いつかなかったので、ソロライブに行って他の人を見るしかなかったです.他の人のコードを見ましたが、考えはまだ分かりませんでした.ネットで他の人の説明の招待状を探して、参考にしました.
ポイントは、一段のサブアレイarr[i]-arr[j]の和がマイナスの場合、この配列の次の要素arr[j+1]を終点とする最大のサブアレイの和が必ずarr[j+1]そのものです.
2つの補助変数を使用すると、
maxTemp
とmaxRes
と、maxTemp
と、今回のループの後に配列される最も大きなサブシーケンスの和と、maxRes
は、配列arrの最も大きなサブシーケンスの和、すなわちテーマが求められていることを示している.for
を用いて、配列arr
を巡回巡回巡回巡回巡回し、要素を1つ取った後、maxTemp
に追加し、maxTemp
より小さいと判断した場合、0
をmaxTemp
に設定し、そうでなければ不変である.その後、0
およびmaxTemp
に行く最大値は、maxRes
に戻りのために与えられる.コード実現(JS)
var maxSequence = function(arr){
// ...
if(arr.length == 0){
return 0;
}
var maxTemp = 0;
var maxRes = 0;
for(var k of arr){
maxTemp += k;
if(maxTemp <0){
maxTemp = 0;
}
maxRes = maxRes >= maxTemp? maxRes : maxTemp;
}
return maxRes;
}
参考資料やはり多く問題をこすって、自分のいくつか思惟の習慣を維持するようにしましょう、頑張って!