24(Nov) Kadane's Algorithm.md

24. Kadane's Algorithm

The problem can be found at the following link: Problem Link

✨ LeetCode Problem of the Day (POTD) Started ✨

• As promised, I’ve continued solving and uploading LeetCode Problem of the Day (POTD) solutions! 🎯
• My latest solution is now live:
  1975. Maximum Matrix Sum

Problem Description

Given an integer array arr[], you need to find and return the maximum sum possible from all the subarrays.

Examples:

Input:
arr[] = [2, 3, -8, 7, -1, 2, 3]
Output:
11

Explanation:
The subarray {7, -1, 2, 3} has the largest sum, which is 11.

Input:
arr[] = [-2, -4]
Output:
-2

Explanation:
The subarray {-2} has the largest sum -2.

Constraints:

• 1 ≤ arr.size() ≤ 10^5
• -10^9 ≤ arr[i] ≤ 10^4

My Approach

1. Kadane's Algorithm:

   • The core idea is to iterate through the array and maintain two variables:
     • maxh: the maximum sum of the subarray that ends at the current index.
     • maxf: the global maximum sum encountered so far.
   • For each element:
     • Update maxh to be either the current element alone (starting a new subarray) or the current element added to the sum of the previous subarray.
     • Update maxf to store the larger value between the current maxf and maxh.
   • The result is the global maximum sum of a subarray in the array.

2. Steps:

   • Initialize maxh to 0 and maxf to a very small value.
   • Traverse the array to calculate the maximum sum of the subarrays.
   • Return maxf as the result, which will hold the largest sum of any subarray.

Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n), where n is the size of the array. The algorithm performs a single linear scan of the array.
• Expected Auxiliary Space Complexity: O(1), as we only use a constant amount of additional space.

Code (C)

#include <limits.h>

long long maxSubarraySum(int arr[], int n) {
    long long maxh = 0, maxf = LLONG_MIN; 

    for (int i = 0; i < n; i++) {
        maxh = (maxh + arr[i] > arr[i]) ? maxh + arr[i] : arr[i];
        maxf = (maxf > maxh) ? maxf : maxh;
    }

    return maxf;
}

Code (Cpp)

class Solution {
public:
    long long maxSubarraySum(vector<int>& arr) {
        long long maxh = 0, maxf = LLONG_MIN;

        for (auto num : arr) {
            maxh = std::max(num + maxh, (long long)num);
            maxf = std::max(maxf, maxh);
        }

        return maxf;
    }
};

👨‍💻 Alternative Approaches

class Solution {
public:
    long long maxSubarraySum(vector<int>& arr) {
        int n = arr.size();
        long long maxh = 0, maxf = LLONG_MIN;
        
        for (int i = 0; i < n; i++) {
            maxh = max((long long)arr[i], maxh + arr[i]);
            maxf = max(maxf, maxh);
        }
        
        return maxf;
    }
};

class Solution {
public:
    long long maxSubarraySum(vector<int>& arr) {
        long long maxh = 0, maxf = LLONG_MIN;

        for (int num : arr) {
            maxh = max((long long)num, maxh + num); 
            maxf = max(maxf, maxh);                
        }

        return maxf;
    }
};

Code (Java)

class Solution {
    public long maxSubarraySum(int[] arr) {
        long maxh = 0, maxf = Long.MIN_VALUE;

        for (int num : arr) {
            maxh = Math.max(num, maxh + num);
            maxf = Math.max(maxf, maxh);
        }

        return maxf;
    }
}

Code (Python)

class Solution:
    def maxSubArraySum(self, arr):
        maxh = 0
        maxf = float('-inf')  

        for num in arr:
            maxh = max(num, maxh + num)
            maxf = max(maxf, maxh)

        return maxf

Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count