Kadane's Algorithm for Largest Subarray Sum:

• Kadane's Algorithm is quite a popular algorithm for finding the largest sum of SubArrays in linear time with constant Space Complexity.
• So now first let's see what are SubArrays:

What are SubArrays:

• As the name suggests, SubArrays are Subset of Arrays or SubArrays are Contiguous part of Arrays.
• Let's look at an example for better understanding:

Problem:

Approaches or Solutions:

1. Naive Approach or Brute Force Approach:

Idea:

• We run two nested loops to traverse each element and for each element, we find its sum with other elements. We update the Maximum Sum as soon as we get a larger value.
• After completion, we will get the maximum sum of the subarray.
• Time Complexity: O(N2) and Space Complexity: O(1) where N = Number of elements in the Array

2. Efficient Approach:

Idea:

• We maintain two pointers, maxSum (For finding maximum Sum) and currSum(For finding current Sum).
• We traverse through the array once and we do the following:
  • If we get the positive element, we add it to currentSum and check if maxSum < currSum:
    • If yes, we update the maxSum to currSum else we just move on
  • If we get a negative element, we initialize currentSum to zero again
• Time Complexity: O(n), Space Complexity: O(1)

3. Modified Kadane's Approach:

• Above approach will return 0 if the entire array is of negative elements, So the only modification will be to initialize maxSum = INT_MIN (INT_MIN is a C++ variable that denotes a huge negative value (-2147483647 - 1)).