MaxSubArray.java


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import java.lang.*;
import java.util.*;

class MaxSubArray {
	public static int maxSubArray(int[] nums) {
		int currSum = 0;
		int maxSum = 0;
		for (int i : nums) {
			currSum = Math.max(currSum + i, 0);
			maxSum = Math.max(maxSum, currSum);
		}
		return maxSum;
	}

	public static void main(String[] args) {
		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		System.out.println(maxSubArray(nums));
	}
}