Given an array of integers, find the sum of a
In the array [-3, 1, -2, 5, 0, 3, 2, -4, 6]
, we can see that the subarray [5, 0, 3, 2, -4, 6]
has a maximum sum of 12, so the output of this program should be 12.
Iterate through the array
Keep track of the current sum and maximum sum encountered so far.
If current sum becomes negative:
Otherwise, continue iterating the array until the end of the array.
After you have iterated through the entire array, return maximum sum.
class Solution { public static int maxSubArray(int[] nums) { int currentSum = 0; // current sum int maximumSum = Integer.MIN_VALUE; // maximum sum to be returned for(int i = 0; i < nums.length; i++) { currentSum = currentSum + nums[i]; if (currentSum > maximumSum) maximumSum = currentSum; // if currentSum is negative ignore // and consider a new subarray if (currentSum < 0) currentSum = 0; } return maximumSum; } public static void main(String[] args) { int array[] = new int[] {-3, 1, -2, 5, 0, 3, 2, -4, 6}; int max = maxSubArray(array); System.out.println(max); } }
The above program uses a greedy approach to continuously maximize the current sum.
Since we are only looping through the array once, the algorithm’s time complexity is $O(n)$, where $n$ is the length of the array.
The space complexity of this algorithm is $O(1)$, as we don’t need any additional memory (other than variables to store currentSum
and maximumSum
).
RELATED TAGS
CONTRIBUTOR
View all Courses