max sum contiguous subsequence Algorithm
The Max Sum Contiguous Subsequence Algorithm is a technique used to find the contiguous subarray within a given array of numbers, which has the largest sum. This problem is commonly known as the Maximum Subarray Problem and has several applications in areas such as image processing, computer vision, and financial market analysis. The algorithm offers an efficient way to solve this problem by employing dynamic programming and works by iterating through the input array while keeping track of the maximum sum found so far and the current sum of the subarray.
The most popular implementation of this algorithm is known as Kadane's Algorithm, which has a linear time complexity of O(n). The algorithm works as follows: initialize two variables, max_sum and current_sum, both initially set to the first element of the array. Then, iterate through the remaining elements in the array, updating the current_sum by adding the current element to it. If the current_sum becomes negative, reset it to zero, as a negative sum would not contribute to the maximum sum subarray. At each step, compare the current_sum with max_sum, updating max_sum if current_sum is larger. After iterating through the entire array, the max_sum variable will contain the largest sum of any contiguous subarray within the input array. This efficient approach allows the algorithm to find the solution in a single pass through the input data, making it an optimal solution for the Maximum Subarray Problem.
def max_subarray_sum(nums: list) -> int:
"""
>>> max_subarray_sum([6 , 9, -1, 3, -7, -5, 10])
17
"""
if not nums:
return 0
n = len(nums)
res, s, s_pre = nums[0], nums[0], nums[0]
for i in range(1, n):
s = max(nums[i], s_pre + nums[i])
s_pre = s
res = max(res, s)
return res
if __name__ == "__main__":
nums = [6, 9, -1, 3, -7, -5, 10]
print(max_subarray_sum(nums))
