連続サブ配列と極値問題
Programming pearls 8 chapter question .
/**
* User: yiminghe
* Date: 2009-2-16
* Time: 15:40:11
*/
public class LongestSubArray {
/**
* [ -1 ,2,3,-5] return 5 [2,3] O(n)
*
* @param a
* @return
*/
public static int getLongestOne(int[] a) {
int max = 0;
int current = 0;
for (int o : a) {
current = Math.max(current + o, 0);
max = Math.max(current, max);
}
return max;
}
/**
* 2 O(m^2n)
* [ -1 ,2,3,-5
* 0 , 3, 5 , 0]
* return 13
* [ 2,3
* 3,5]
*
* @param a2 2
* @param m
* @param n
* @return
*/
public static int getLongestTwo(int[][] a2, int m, int n) {
int[][] cache = new int[m][n + 1];
int max = 0;
for (int i = 0; i < m; i++) {
cache[i][0] = 0;
for (int j = 1; j < n + 1; j++) {
cache[i][j] = cache[i][j - 1] + a2[i][j - 1];
}
}
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++) {
int[] t = new int[m];
for (int k = 0; k < m; k++) {
t[k] = cache[k][j + 1] - cache[k][i];
}
max = Math.max(max, getLongestOne(t));
}
return max;
}
public static void main(String[] args) {
int[] a = {-1, 2, 3, -5};
int[][] b = {{-1, 2, 3, -5}, {0, 3, 5, 0}};
System.out.println(getLongestOne(a));
System.out.println(getLongestTwo(b, 2, 4));
}
}