Kadane's Algorithm For Maximum Subarray Sum
Kadane's Algorithm finds maximum sum of continuous subarray in O(n) time complexity and O(1) space complexity. It iterates through array, updating current sum and max sum as needed.
Kadane's Algorithm is one of the algorithms to efficiently find maximum sum of continuous subarray.
problem
Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.
Example 1:
Input:
N = 5
Arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which
is a contiguous subarray.
TC:
O(n)O(n)O(n)
SC:
O(1)O(1)O(1)
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
int currentSum = 0;...