这篇文章主要介绍“Java怎么求一个整型数组中最大连续子序列的和”，在日常操作中，相信很多人在Java怎么求一个整型数组中最大连续子序列的和问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java怎么求一个整型数组中最大连续子序列的和”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
/**
动态规划(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怎么求一个整型数组中最大连续子序列的和”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/1399755/blog/1829216
