53. Maximum Subarray

📝 Problem Details

• Title: 53. Maximum Subarray
• Link: https://leetcode.com/problems/maximum-subarray/
• Difficulty: Medium
• Tags/Categories: Greedy

input array nums find the subarray with the largest sum return its sum

💭What Were My Initial Thoughts?

brute force solution would involve backtracking across all possible subarrays, keeping track of a max sum value and returning it 

the sum of a subarray can be used to determine the sum of a larger subarray that contains those elements
we can cache the results of these to avoid recompuation

maybe a 2d dp table where dp[i][j] represents the sum of the subarray from [i:j]

--------
intuition is possible but there is a more optimal solution using Kadane's Algorithm that is a greedy approach

🤔What Did I Struggle With?

was unable to come up with greedy approach intuitively

💡 Explanation of Solution

Kadane's Algorithm:
- at each index i, we decide greedily whether to:
	1. extend the previous subarray (currSum + nums[i])
	2. start fresh with a new subarray (nums[i])
- the greedy decision ensures that we always keep the best possible sum ending at i

⌛ Complexity Analysis

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

💻 Implementation of Solution

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0], currSum = nums[0];
 
        for (int i = 1; i < nums.size(); i++) {
            currSum = max(nums[i], currSum + nums[i]);  // Extend or restart
            maxSum = max(maxSum, currSum);
        }
 
        return maxSum;
    }
};