Skip to main content

Maximum Subarray

Problem​

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

A subarray is a contiguous part of an array.

Solution Approach​

Can we solve it using kadane's Algorithm?

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    int maxSubArray(vector<int>& nums) {
        int ans = *max_element(nums.begin(), nums.end());
        int n = nums.size();
        int max_so_far = 0, max_till_here = 0;

        for (int i = 0; i < n; i++) {
            max_till_here += nums[i];
            if (max_till_here > max_so_far) max_so_far = max_till_here;
            if (max_till_here < 0) max_till_here = 0;
        }
        if (ans < 0) return ans;
        return max_so_far;
    }
};