Kadane’s Algorithm

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.

• Time : O(n)
• Space : O(1)

class Solution{
    public:
    // arr: input array
    // n: size of array
    //Function to find the sum of contiguous subarray with maximum sum.
    long long maxSubarraySum(int arr[], int n){
        long long res = arr[0], sum = 0;
        for(int i = 0; i < n; i++) {
            sum = max(sum + arr[i], (long long)arr[i]);
            res = max(res, sum);
        }
        
        return res;
    }
};