Problem:
Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum.
For Example:
Given input: [-2,1,-3,4,-1,2,1,-5,4],
output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Solution:
We can iterate the array, add the current number to the sum. If the sum is negative, we don't want to carry it to calculate the total with the next number, whenever we get a negative sum, we want to start over, because adding a negative number only makes the total smaller.
In case all the numbers are non-positive, we return the largest negative number, in another words, we don't sum up negative numbers.
class Solution {
public static void main(String...args) {
int[] arr = new int[]{-2,1,-3,4,-1,2,1,-5,4};
System.out.println(largestSum(arr));
}
public static int largestSum(int[] arr) {
int max = Integer.MIN_VALUE;
int count = 0;
for(int i = 0; i < arr.length; i++) {
count += arr[i];
if(count > 0) {
max = Math.max(max, count);
}
else {
max = Math.max(max, arr[i]);
count = 0;
}
}
return max;
}
}
The time complexity is O(N), the space complexity is O(1).
public static void main(String...args) {
int[] arr = new int[]{-2,1,-3,4,-1,2,1,-5,4};
System.out.println(largestSum(arr));
}
public static int largestSum(int[] arr) {
int max = Integer.MIN_VALUE;
int count = 0;
for(int i = 0; i < arr.length; i++) {
count += arr[i];
if(count > 0) {
max = Math.max(max, count);
}
else {
max = Math.max(max, arr[i]);
count = 0;
}
}
return max;
}
}
