这篇文章主要介绍“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怎么求一个整型数组中最大连续子序列的和”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。