<jupyter_start><jupyter_text>Find maximum sum subarray> Given an array, find contigous subarray that has maximum sum- toc: false- badges: true- comments: true- categories: [array, dynamic programming]  ProblemGiven an array, find a subarray (contigous element in array) that has maximum sum. Example:```Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]Output: 6The sum of subarray [4, -1, 2, 1] is 6 which is maximum of all subarray possible```  SolutionKadane's algorithm {% cite wiki_kadane %} scan's the given array and maintains maximum sum at all the index.<jupyter_code>def max_sum_subarray(nums):
    # stores the maximum sum sublist found so far
    max_so_far = nums[0]
 
    # stores the maximum sum of sublist ending at the current position
    max_ending_here = nums[0]
 
    # traverse the given list
    for num in nums[1:]:
        # update the maximum sum of sublist "ending" at index `i`
        max_ending_here = max_ending_here + num
 
        # maximum sum should be more than the current element
        max_ending_here = max(max_ending_here, num)
 
        # update the result if the current sublist sum is found to be greater
        max_so_far = max(max_so_far, max_ending_here)
 
    return max_so_far
#collapse-hide
nums = [-2, -1, -3, -4, -1, -2, -1, -5, -4]
print(f"Max sum subaary of {nums} = {max_sum_subarray(nums)}")
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(f"Max sum subaary of {nums} = {max_sum_subarray(nums)}")<jupyter_output>Max sum subaary of [-2, -1, -3, -4, -1, -2, -1, -5, -4] = -1
Max sum subaary of [-2, 1, -3, 4, -1, 2, 1, -5, 4] = 6
{'fraction_non_alphanumeric': 0.12030553787396563, 'fraction_numerical': 0.03564608529598982, 'mean_word_length': 3.318681318681319, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '658780', 'license': 'Apache-2.0', 'n_tokens_mistral': 601, 'n_tokens_neox': 558, 'n_words': 216, 'path': '_notebooks/2021-02-19-max-subarray-kadane-algo.ipynb', 'repo_name': 'projekt2k22/codebook', 'size': '1571'}