1.Maximum Subarray Sum

Given an integer array, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6

Solution :

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int sum = 0, maxSum = INT_MIN;
        for (int i = 0; i < nums.size(); i++)
        {
            sum = sum + nums[i];
            
            if (sum > maxSum)
            {
                maxSum = sum;
            }

            if (sum < 0)
            {
                sum = 0;
            }
        }
        return maxSum;
    }
};

Time Complexity: O(n) using Kadane's Algorithm