-
Notifications
You must be signed in to change notification settings - Fork 1.8k
/
LargestSumContiguousSubarray.java
36 lines (31 loc) · 1.07 KB
/
LargestSumContiguousSubarray.java
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
31
32
33
34
35
36
package com.jwetherell.algorithms.sequence;
/**
* Given an array of integers, we want to find the largest sum of contiguous
* subarray.
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem">Maximum Subarray Problem (Wikipedia)</a>
* <br>
* @author Miguel Stephane KAKANAKOU <[email protected]>
* @author Justin Wetherell <[email protected]>
*/
public class LargestSumContiguousSubarray {
private LargestSumContiguousSubarray() { }
/**
* Largest sum of contiguous subarray using Kadane's algorithm.
*
* @param A
* the given Array of integer
* @return
*/
public static int getLargestSumContiguousSubarray(int[] A) {
if (A == null)
throw new NullPointerException("The given array is null");
int max_so_far = A[0];
int max_ending_here = A[0];
for (int i = 1; i < A.length; i++) {
max_ending_here = Math.max(A[i], max_ending_here + A[i]);
max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
}