charles901030
BAN USERpublic static int[] maxSubArrayEpic(int[] A) {
if (A.length <= 2 || A == null) {
return A;
}
int[] dp = new int[A.length];
dp[0] = A[0];
// use dp array to store the max sum of subarray
for (int i = 1; i < A.length; i++) {
dp[i] = Math.max(A[i], dp[i - 1] + A[i]);
}
int max = dp[0];
int index = 0;
// iterate dp array to find the max index;
for (int i = 1; i < dp.length; i++) {
if (dp[i] > max) {
index = i;
max = dp[i];
}
}
// use list to add the element of max subarray
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(A[index]);
if (index - 1 > 0) {
for (int i = index - 1; i >= 0; i--) {
if (dp[i] < 0) {
break;
}
list.add(A[i]);
}
}
int[] result = new int[list.size()];
for (int i = result.length - 1; i >= 0; i--) {
result[i] = list.get(i);
}
if (result.length == 1) {
result = new int[2];
int maxPair = Integer.MIN_VALUE;
int start = 0;
int end = 0;
for (int i = 1; i < A.length; i++) {
if (A[i] + A[i - 1] > maxPair) {
start = i - 1;
end = i;
maxPair = A[i] + A[i - 1];
}
}
result[0] = A[start];
result[1] = A[end];
}
return result;
}
why so many people use DP ?
- charles901030 October 18, 2014Can DP find all longest paths?