#はじめに
おはようございます．
M1就活生がLeetCodeから，easy問題を中心にPythonを用いて解いていきます．
↓では，解いた問題のまとめを随時更新しています．
まとめ記事
#問題
今回解いたのは，難易度easyから 問題53のMaximum Subarray です．
問題としては，整数配列numsが与えられたとき，最大の和を持つ連続した部分配列を見つけ，その和を返すというもの．
入力例と出力例は以下の通りです．
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
#書いたコード
始めに書いたコードが以下で，こちらのコードでは，Time Limit Exceededとなりました．2重で繰り返し処理を行い，整数配列numsの先頭から順に部分配列を求めていくものになります．こちらのコードでは，numsの要素数が少ない場合，少ない計算時間で済みますが，大きすぎる場合，計算処理に相当時間がかかってしまいます．そのため，効率の良い処理を書く必要があります．
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = nums[0]
for i in range(len(nums)):
for j in range(len(nums) - i):
subarray_sum = sum(nums[i:i+j+1])
if max_sum < subarray_sum:
max_sum = subarray_sum
return max_sum
どうにか，繰り返し処理を1回のみ使って書き直してみます．上のコードでは，numsの0番目要素から計算していましたが，今回は部分配列をnumsの0番目要素で初期化し，numsの1番目以降の要素（次の要素）を基準に，部分配列の和を計算しています（+nums[i:i+j+1]の1って何を防げる）．
繰り返し処理では，numsの1番目以降を走査していきます．今回の問題は，”現在の部分配列+次の要素”と”次の要素”を比較し，その結果が大きいほうを次の部分配列の数としていきます．6〜9行目がその処理です．これで，得られた数と，現在の最大の和を比較することで部分配列の最大の和を見つけることができます．
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
subarray_sum = max_sum = nums[0]
for num in nums[1:]:
if num < subarray_sum + num:
subarray_sum = subarray_sum + num
else:
subarray_sum = num
if max_sum < subarray_sum:
max_sum = subarray_sum
return max_sum
#おわりに
Pythonのリスト操作では，範囲外を参照した場合，IndexErrorとなります．しかし，スライスを使った場合にはこのエラーは出ず，うまく処理してくれます．スライスの範囲指定が間違っていても気が付かない場合があるため，注意する必要がありますね．
今回書いたコードはGitHubにもあげておきます．