Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Solution
We can do level order traversal, instead of Queue we can use Stack to maintain the next level for the ZigZag pattern.
Code
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
public class MaximumSubArray { public static void main(String[] args) { int a[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 }; System.out.println(new MaximumSubArray().maxSubArray(a)); } public int maxSubArray(int[] nums) { if (nums.length == 0) return 0; int max_so_far = Integer.MIN_VALUE, max_ending_here = 0; for (int i = 0; i < nums.length; i++) { max_ending_here = max_ending_here + nums[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; } return max_so_far; } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.
