
与えられた配列のうち、連続した部分配列の和の最大値を求める問題を考える(最大部分配列問題、最大部分列和問題)。
愚直に解くと二重ループだが、O(n^2)となり遅い。
DPの一種であるKadane’s algorithmを使うとO(n)で高速に解けるようになる。
試しにLeetCodeの53. Maximum Subarrayを解いてみる。

Maximum Subarray - LeetCode
Maximum Subarray - Given an integer array nums, find the subarray which has the largest sum and return its sum. Example 1: Input: nums = Output: 6 Explan...
愚直解:O(n^2)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
ans = -1e5
for i in range(n):
for j in range(n):
if j < i:
continue
temp = nums[i:j+1]
ans = max(ans, sum(temp))
return ans
Kadane’s algorithm O(n)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
best = -1e9
cur = 0
for i in range(len(nums)):
cur = max(nums[i], nums[i] + cur)
best = max(best, cur)
return best
参考
Easy Python Way - LeetCode Discuss
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Maximum subarray problem - Wikipedia

Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?
If you are here, then chances are that you were trying to solve the “Maximum Subarray Problem” and came across Kadane’s Algorithm but…
コメント