Kadane's Algorithm

Explanation

- Kadane’s Algorithm is used to find the **maximum sum subarray** in a given array of integers. It works in **O(n)** time.

-

• Steps

  • Initialize two variables: current_sum and max_sum.
  • Traverse through the array, adding each element to current_sum.
  • If current_sum becomes negative, reset it to 0.
  • Update max_sum to the maximum value between max_sum and current_sum.

• Time Complexity

  • O(n), where n is the number of elements in the array.