【codewars】Maximum subarray sum【最大サブシーケンスの和を求める】


テーマ
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つの補助変数を使用すると、maxTempmaxResと、maxTempと、今回のループの後に配列される最も大きなサブシーケンスの和と、maxResは、配列arrの最も大きなサブシーケンスの和、すなわちテーマが求められていることを示している.forを用いて、配列arrを巡回巡回巡回巡回巡回し、要素を1つ取った後、maxTempに追加し、maxTempより小さいと判断した場合、0maxTempに設定し、そうでなければ不変である.その後、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;
}
参考資料
  • https://www.jianshu.com/p/4edab8dbea9f
  • 結びのことば
    やはり多く問題をこすって、自分のいくつか思惟の習慣を維持するようにしましょう、頑張って!