Maximum Subarray Sum in Java

When working with arrays, one common problem is finding the maximum sum of a subarray. A subarray is simply a continuous part of the array. The goal is to pick a portion of the array such that the sum of its elements is as large as possible. Understanding the Problem Given an integer array, which may contain both positive and negative numbers, we need to find the maximum possible sum of any continuous subarray. For example Array: [−2, 1, −3, 4, −1, 2, 1, −5, 4] Output: 6 Explanation: The subarray [4, −1, 2, 1] gives the maximum sum. Simple Idea The best way to solve this problem is using a method called Kadane’s Algorithm. The idea is simple: At each step, decide whether to: Continue the current subarray Start a new subarray from the current element We keep track of: Current sum of subarray Maximum sum found so far Algorithm Steps Start with two variables: currentSum = first element maxSum = first element Traverse the array from the second element For each element: Add it to currentSum