共计 2014 个字符，预计需要花费 6 分钟才能阅读完成。

这篇文章主要介绍“Java 怎么求一个整型数组中最大连续子序列的和”，在日常操作中，相信很多人在 Java 怎么求一个整型数组中最大连续子序列的和问题上存在疑惑，丸趣 TV 小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java 怎么求一个整型数组中最大连续子序列的和”的疑惑有所帮助！接下来，请跟着丸趣 TV 小编一起来学习吧！

/**

动态规划 (Dynamic Programming)：

 1) 将待求解的问题分解为若干个子问题 (即: 将求解的过程分为若干阶段)，按顺序求解子问题，前一子问题的解，为后一子问题的求解提供了有用的信息；

 2) 在求解任一子问题时，列出可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其它的局部解；

 3) 依次解决各子问题，最后一个子问题的解就是初始问题的解。

问题：求一个整型数组中最大连续子序列的和，数组中既包含正整数也包含负整数。

举例：数组 int[] array = {1, -3, 7, 8, -4, 10, -19, 11}; 中最大连续子序列为：7, 8, -4, 10 它们的和为 21

*/

public class DP {
 *  暴力求解
 *
 *  时间复杂度：O(N^2)
 */
public static int maxSubSumByEnum(int[] array) {
 int maxSum = 0;
 int begin = 0;
 int end = 0;
 /**
 * 1) 第 i 次循环结束后可以找到：以第 i 个元素为起点的连续子序列的最大值。 * 2)i 表示序列的起点，j 表示序列的终点。 * 3) 每一次循环中将终点不断向后移动：每次向后移动一位并且计算当前序列的和，循环结束后，我们就可以得到本次循环中子序列和最大的值。 */
 for (int i = 0; i   array.length; i++) { //
 int tempSum = 0;
 for (int j = i; j   array.length; j++) { tempSum += array[j];
 if (tempSum   maxSum) {
 maxSum = tempSum;
 begin = i;
 end = j;
 }
 }
 }
 System.out.println(begin:  + begin +   end:  + end);
 return maxSum;
 *  动态规划
 *
 *  时间复杂度：O(N)
 *
 *  要点： * 1) 若当前阶段中连续子序列的和小于 0，则进入下一阶段，同时确定下一阶段的起点并将下一阶段的和初始化为 0。 * 2) 只有当前阶段的总和大于历史最大总和时，才会去更新数组中最大连续子序列的起点和终点。 */
public static int maxSubSumByDP(int[] array) {
 int maxSum = 0; //  数组中，最大连续子序列的和
 int begin = 0; //  数组中，最大连续子序列的起点
 int end = 0; //  数组中，最大连续子序列的终点
 int tempSum = 0; //  当前阶段中，连续子序列的和
 int tempBegin = 0; //  当前阶段中，连续子序列的起点
 for (int i = 0; i   array.length; i++) { tempSum += array[i];
 if (tempSum   0) { //  若当前阶段中连续子序列的和小于 0，则进入下一阶段
 tempSum = 0; //  下一阶段的和进行归零处理
 tempBegin = i + 1; //  下一阶段的起点
 } else if (tempSum   maxSum) { //  若当前阶段的总和大于历史最大总和，则更新数组中最大连续子序列的起点和终点。 maxSum = tempSum;
 begin = tempBegin;
 end = i;
 }
 }
 System.out.println(begin:  + begin +   end:  + end);
 return maxSum;
public static void main(String[] args) { int[] array = {1, -3, 7, 8, -4, 10, -19, 11};
 int dpMax = maxSubSumByDP(array);
 System.out.println(dpMax);
 int enumMax = maxSubSumByEnum(array);
 System.out.println(enumMax);
}

}

到此，关于“Java 怎么求一个整型数组中最大连续子序列的和”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注丸趣 TV 网站，丸趣 TV 小编会继续努力为大家带来更多实用的文章！