Leetcode 53 Maximum Subarray
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.
Ana paterni bulalım.Ana mantık elimizdeki sayıyı toplamı en büyük olan kümeye eklemek. Eğer yeni toplam kümesi önceki toplam kümeden büyükse yeni toplam kümesini en büyük toplam küme yaparız. dp[i] = max(dp[i-1]+nums[i], nums[i]) Eğer yeni toplam kümesi önceki toplam kümeden küçükse önceki en büyük toplam kümesini bırakır şu anki sayı ilk index olacak şekilde yeni bir kümeye başlarız.
def maxSubArray(self, nums: List[int]) -> int:
dp = [0]*len(nums)
dp[0] = nums[0]
max_num = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1]+nums[i], nums[i])
if dp[i]>max_num: max_num = dp[i]
return max_num
def maxSubArray(self, nums: List[int]) -> int:
if max(nums)<0:
return max(nums)
curr_sum, max_sum = 0, 0
for num in nums:
curr_sum = max(0, curr_sum + num)
max_sum = max(curr_sum, max_sum)
return max_sum