<jupyter_start><jupyter_text>Maximum SubarrayGiven an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.A subarray is a contiguous part of an array..From [Leetcode](https://leetcode.com/problems/maximum-subarray/).<jupyter_code>from math import inf

def MaxSubarray(nums):
  maxsum = -inf
  for i in range(len(nums)):
    currsum = 0
    for j in range(i, len(nums)):
      currsum += nums[j]
      if currsum > maxsum:
        maxsum = currsum

  return maxsum


MaxSubarray([-2,-11,-13,-2,-14,-9,-5,-15,-3])
MaxSubarray([-2,1,-3,4,-1,2,1,-5,4])<jupyter_output><empty_output><jupyter_text>Kadane's Algorithm<jupyter_code>from math import inf

def MaxSubarray3(nums):
  best_sum = -inf
  curr_sum = 0
  for i in nums:
    curr_sum = max(i, curr_sum+i)
    best_sum = max(curr_sum, best_sum)
    
      
  return best_sum


MaxSubarray3([-1])<jupyter_output><empty_output><jupyter_text>Divide And Conquer<jupyter_code>from math import inf as infinity

def maxSumSubarray(nums, low, high):
  if low==high:
    return nums[0]

  mid = (low+high)//2
  leftMaxSubarray = maxSumSubarray(nums, low, mid)
  rightMaxSubarray = maxSumSubarray(nums, mid+1, high)

  rightsum = -infinity
  leftsum = -infinity

  sum = 0
  #print("mid", mid)
  for i in range(mid):
    sum += nums[i]
    leftsum = max(sum, leftsum)


  sum = 0

  for i in range(mid, len(nums)):
    sum += nums[i]   
    rightsum = max(sum, rightsum)



  ans = max(leftMaxSubarray, rightMaxSubarray)
  #print("ans",ans)
  #print("r+l",rightsum+leftsum)
  return max(ans, rightsum+leftsum)

nums = [5,4,-1,7,8]
maxSumSubarray(nums, 0, len(nums))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13348946135831383, 'fraction_numerical': 0.02224824355971897, 'mean_word_length': 4.041297935103245, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 14, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '396188', 'license': 'Apache-2.0', 'n_tokens_mistral': 695, 'n_tokens_neox': 661, 'n_words': 152, 'path': 'Maximum Subarray/Maximum_Subarray.ipynb', 'repo_name': 'LucasColas/Coding-Problems', 'size': '1708'}