Maximum SubArray Sum Problem LeetCode

 Given an integer array nums, find the subarray with the largest sum, and return its sum.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]

Output: 1

Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Correct Approach (Kadane’s Algorithm)

We need:

1. A variable currentSum to track the running sum.
2. A variable maxSum to store the maximum encountered sum.
3. If currentSum becomes negative, reset it to 0.

class Solution {

    public int maxSubArray(int[] nums) {

       

    int maxSum = nums[0];  // Initialize with first element

        int currentSum = 0;

        for (int num : nums) {

            if (currentSum < 0) {

                currentSum = 0;  // Reset if negative

            }

            currentSum += num;

            maxSum = Math.max(maxSum, currentSum);  // Update max sum

        }

        return maxSum;

    }

}