最大连续子数组的积
最大连续子数组的积
不考虑溢出，注意多个0，多个负数，还有结果是1的情况
public class MaxSubMultiplication { public static int calculate(int[] array) { int lastZeroIndex = -1; int indexOfFirstNegative = -1; int indexOfLastNegative = -1; int mulBeforeFirst = 1; int mulAfterLast = 1; int mulOfAll = 1; boolean hasPositive = false; int max = 0; for (int i = 0; i < array.length; i++) { if (array[i] == 0) { if (mulOfAll > 0) { if (max < mulOfAll) max = mulOfAll; } else if (mulOfAll < 0) { for (int j = lastZeroIndex + 1; j <= indexOfFirstNegative - 1; j++) { mulBeforeFirst *= array[j]; } for (int k = indexOfLastNegative + 1; k <= i - 1; k++) { mulAfterLast *= array[k]; } int cadidateOne = (mulOfAll / mulBeforeFirst) / array[indexOfFirstNegative]; int cadidateTwo = (mulOfAll / mulAfterLast) / array[indexOfLastNegative]; int result = maxOfFour(mulBeforeFirst, mulAfterLast, cadidateOne, cadidateTwo); if (max < result) max = result; } lastZeroIndex = i; indexOfFirstNegative = -1; indexOfLastNegative = -1; mulBeforeFirst = 1; mulAfterLast = 1; mulOfAll = 1; } else { if (array[i] < 0) { if (indexOfFirstNegative < 0) indexOfFirstNegative = i; indexOfLastNegative = i; } mulOfAll *= array[i]; if (mulOfAll > 0 || array[i] > 0) hasPositive = true; } } if (mulOfAll > 0) { if (max < mulOfAll) max = mulOfAll; } else if (mulOfAll < 0) { for (int j = lastZeroIndex + 1; j <= indexOfFirstNegative - 1; j++) { mulBeforeFirst *= array[j]; } for (int k = indexOfLastNegative + 1; k <= array.length - 1; k++) { mulAfterLast *= array[k]; } int cadidateOne = (mulOfAll / mulBeforeFirst) / array[indexOfFirstNegative]; int cadidateTwo = (mulOfAll / mulAfterLast) / array[indexOfLastNegative]; int result = maxOfFour(mulBeforeFirst, mulAfterLast, cadidateOne, cadidateTwo); if (max < result) max = result; } return (max != 1) ? max : (hasPositive ? max : 0); } private static int maxOfFour(int a, int b, int c, int d) { int max = a; if (max < b) max = b; if (max < c) max = c; if (max < d) max = d; return max; } public static void main(String[] args) { int[] array = { -1, 0, -2, 1, 0, -6, 0, -7 }; System.out.println(MaxSubMultiplication.calculate(array)); }}?
?