（ブログ記事からの転載）
[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のソースコードも載っていますが、説明もなく丸写しもなんなので、ひとまずリンクを示すに留めます。
[https://www.geeksforgeeks.org/maximum-subarray-sum-using-divide-and-conquer-algorithm/]