LeetCode / Maximum Subarray - オットセイの経営日誌

https://leetcode.com/problems/search-insert-position/

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

integerのlistの中で、和が最も大きくなる部分的なlist(subarray)の和を求める問題です。
所謂Dynamic Programming（動的計画法）の分野では有名な例題のようですね。
計算量 $O(n)$ の方法が見つかったら、次は divide and conquer approach（日本語では分割統治法）を試してみろ、と言われていますが、現時点で何のことやら、、、という感じなので、プレーンな方法のみ示します。

解答・解説

解法1

listに対してloopを回して探索していきますが、入力numsに対して、subarrayの和を一時的に格納しておく変数curSumと、探索した中で最大のsubarrayの和を格納しておく変数maxSumを用意します。
curSumの計算方法が若干分かりにくいですが、初期値はcurSum = nums[0]とし、ループの中で curSum = max(num, curSum + num) とすることで、listの次の要素を足した値と、次の要素単体の値を比べ、大きい方の値でcurSumを更新します。
例えばnums = [-1,2,-1,4]であれば、(curSum, maxSum)は、(-1,-1), (2, 2), (2-1, 2), (2-1+4, 5)と変わっていきます。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0

        curSum = maxSum = nums[0]
        for num in nums[1:]:
            curSum = max(num, curSum + num)
            maxSum = max(maxSum, curSum)

        return maxSum

解法2（のreference）

divide and conquer approachですが、以下サイトが参考になりそう。
Pythonのソースコードも載っていますが、説明もなく丸写しもなんなので、ひとまずリンクを示すに留めます。