##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Kadane's algorithm
Kadane's algorithm maintains the maximum sum ending at each position. If adding the current element makes the sum negative, restart. Initialize , . For each element: , then . Example: . The maximum subarray is with sum . Time: , Space: . This is optimal for the problem.
Time complexity: .
Space complexity: .
