最大子序列原始问题是指一串连续的数字，从中找出和最大的连续字串的和。
此处列出一些简单的解法以及关于这个问题的一些衍生问题。
O(N3)解法：
1 public class MaxSubsequenceSum 2 { 3 public static int getMaxSubsequenceSum(int[] array) 4 { 5 int maxSum = 0; 6 7 for(int i = 0; i < array.length; i++) 8 for(int j = i; j < array.length; j++) 9 {10 int thisSum = 0;11 12 for(int k = i; k <= j; k++)13 thisSum += array[k];14 15 if(thisSum > maxSum)16 maxSum = thisSum;17 }18 19 return maxSum;20 }21 }
O(N2)解法：
1 public class MaxSubsequenceSum 2 { 3 public static int getMaxSubsequenceSum(int[] array) 4 { 5 int maxSum = 0; 6 7 for(int i = 0; i < array.length; i++) 8 { 9 int thisSum = 0;10 11 for(int j = i; j < array.length; j++)12 {13 thisSum += array[j];14 15 if(thisSum > maxSum)16 maxSum = thisSum;17 }18 }19 20 return maxSum;21 }22 }
O(NlogN)解法（递归解法）：
1 public class MaxSubsequenceSum 2 { 3 public static int getMaxSubsequenceSum(int[] array, int left, int right) 4 { 5 if(left == right) 6 if(array[left] > 0) 7 return array[left]; 8 else 9 return 0;10 11 int center = (left + right) / 2;12 int maxLeftSum = getMaxSubsequenceSum(array, left, center);13 int maxRightSum = getMaxSubsequenceSum(array, center + 1, right);14 15 int maxLeftBorderSum = 0, leftBorderSum = 0;16 for(int i = center; i >= left; i--)17 {18 leftBorderSum += array[i];19 if(leftBorderSum > maxLeftBorderSum)20 maxLeftBorderSum = leftBorderSum;21 }22 23 int maxRightBorderSum = 0, rightBorderSum = 0;24 for(int i = center + 1; i <= right; i++)25 {26 rightBorderSum += array[i];27 if(rightBorderSum > maxRightBorderSum)28 maxRightBorderSum = rightBorderSum;29 }30 31 return Math.max(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);32 }33 }
O(N)解法：
1 public class MaxSubsequenceSum 2 { 3 public static int getMaxSubsequenceSum(int[] array) 4 { 5 int thisSum = 0; 6 int maxSum = 0; 7 8 for(int i = 0; i < array.length; i++) 9 {10 thisSum += array[i];11 12 if(thisSum > maxSum)13 maxSum = thisSum;14 else if(thisSum < 0)15 thisSum = 0;16 }17 18 return maxSum;19 }20 }
以上是对于最大子序列和的几种解法，以下有一些相关问题：
最小子序列：
1 public class MinSubsequenceSum 2 { 3 public static int getMinSubsequenceSum(int[] array) 4 { 5 int thisSum = 0; 6 int minSum = 0; 7 8 for(int i = 0; i < array.length; i++) 9 {10 thisSum += array[i];11 12 if(thisSum < minSum)13 minSum = thisSum;14 else if(thisSum > 0)15 thisSum = 0;16 }17 18 return minSum;19 }20 }
最小正子序列：
1 public class MinPositiveSubsequenceSum 2 { 3 public static int getMinPositiveSubsequenceSum(int[] array) 4 { 5 int thisSum = 0; 6 int minPositiveSum = array[0]; 7 8 for(int i = 0; i < array.length; i++) 9 {10 thisSum += array[i];11 12 if(thisSum < minPositiveSum && thisSum > 0)13 minPositiveSum = thisSum;14 else if(thisSum < 0)15 minPositiveSum = 0;16 }17 18 return minPositiveSum;19 }20 }
最大乘积子序列：
1 public class MaxSubsequenceProduct 2 { 3 public static int getMaxSubsequenceProduct(int[] array) 4 { 5 int thisProduct = 1; 6 int maxProduct = 1; 7 8 for(int i = 0; i < array.length; i++) 9 {10 thisProduct *= array[i];11 12 if(thisProduct > maxProduct)13 maxProduct = thisProduct;14 else if(thisProduct < 1)15 thisProduct = 1;16 }17 18 return maxProduct;19 }20 }