こんにちは
今回の学びは
・「次のこの問題を解くばあい知っていればよい一つの事実とは？」でフックを増やせ
・解きまくって量を増やしてひらめきを早くしよう！
・で、連続するなになにとくれば、それまでの合計を持ち歩くことができそうです
・kadane方式です。index J で終わるサブ配列を考えるのが味噌
問題はeasyですが、mediumくらいは有る感じです。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
なんどもサンプルを汚して
ようやく思いつく問題にはどうしたら
もっと早くおもいつくのか？
もっと早くとけるのか？
これには焦らず、量とフックを増やしましょう。（ひらめく方法のググり結果を参照）
量はleetcodeやatcoderなどの問題を数多く解くこと
フックは、毎回その問題から「次のこの問題を解くばあい知っていればよい一つの事実とは？」と （※１）
自問してその答えを用意しておこう
持ちろん、本記事のように学びを抽出していくことも効果はあるとおもう。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
実際の実装はこちら
import sys
sys.setrecursionlimit(314159265)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pre = -sys.maxsize
i = 0 # left pointer
total = 0
maxi = -sys.maxsize
for j in range(len(nums)):
curr = nums[j]
#print("i:%s, j:%s, curr:%s, total:%s" % (i, j, curr, total))
if total + curr > curr:
#print("継続")
total += curr
maxi = max(maxi, total)
elif total + curr < curr:
#print("一回リセットししょ")
maxi = max(maxi, total)
total = curr
maxi = max(maxi, total)
i = j
else:
#print("まぁ継続")
total += curr
maxi = max(maxi, total)
pre = curr
# 最後にもう一回しておく必要がある
maxi = max(maxi, total)
return maxi
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
これまで、と現在を比較、悪い過去は切り捨て戦法、となづけました
最後に考えがごちゃついている実装なので掃除したバージョンをアップします
こちら
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
total = 0
maxi = -2147483647
for j in range(len(nums)):
curr = nums[j]
past = total + curr
if past > curr:
total += curr
elif past < curr:
total = curr
else:
total += curr
maxi = max(maxi, total)
return maxi
変数大事〜
pastにしただけでだいぶ読みやすくなったし
あとこの問題
contiguous(隣接する）とあります
連続すると、捉えてもいいです。
で、連続するなになにとくれば、それまでの合計を持ち歩くことができそうです
と、ここまでが最初の記事だったのですが、この最初の記事から4ヶ月ぶりにこの問題に
再び向かったのですが、残念ながら全く解けませんでしたw。
解法はいくつかあります。leetcodeのソリューションはこちらです。
分割統治法(devide and concur)と
greedyと
Dynamic Programming で、このmaxium subarrayにおいては kadane's algorithm という名前がついているものです。
kadane's algorithm は説明動画はこちらがわかりやすかったです。Dynamic Programmingで縦軸に同じく配列を撮って
starting indexとしてi-thからサブ配列を始めた時のmaxSubarrayと自然にしたいところですが、これだとO(N^2)でBFと変わりません。そこで、
要素が連続という点と、うまく以前の結果を再利用という、ヒントから
f(i) = f(i - 1) + nums[i] 的な式を立てたのが、kadane方式です。index J で終わるサブ配列を考えるのが味噌で、
これによってO(N)で処理が終わります
kadaneの実装はこちら
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
N = len(nums)
if N == 0: return 0
dp = [0] * N
dp[0] = nums[0]
maxi = nums[0]
for i in range(1, N):
dp[i] = max(
dp[i-1] + nums[i],
nums[i]
)
maxi = max(maxi, dp[i])
return maxi
devide and concurはこちらの説明動画をみて理解しました。
まとめ
・「次のこの問題を解くばあい知っていればよい一つの事実とは？」でフックを増やせ
・解きまくって量を増やしてひらめきを早くしよう！
・で、連続するなになにとくれば、それまでの合計を持ち歩くことができそうです
・kadane方式です。index J で終わるサブ配列を考えるのが味噌
以上です