Java实现求子数组和的最大值算法示例
本文实例讲述了Java实现求子数组和的最大值算法。分享给大家供大家参考,具体如下:
一般C和C++在算法实现中使用较多,下面我们通过java语言实现算法,更有亲切感。
题目:
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。
实现代码:
package arrDemo; public class MaxSub { public static void main(String[] args) { // TODO 自动生成的方法存根 findMaxSubArySum1(); } public static void findMaxSubArySum1() { // sum为子数组的和 int sum = 0; // max为子数组的最大和 int max = 0; // 最大子数组的起始位置 int startPos = 0; // 最大子数组的结束位置 int endPos = 0; int[] array = { -1, 2, -3, 12, -5, -1, 9, -2 }; for (int i = 0; i < array.length; i++) { sum += array[i];// 求和 if (sum < 0) {// 如果当前求得总和为负数的话,就将其清零,并且开始位置从下一个位置开始 sum = 0; startPos = i + 1; } if (sum > max) {// 如果求得总和大于之前的最大值的话,就将sum赋值给max,同时记录最后的位置 max = sum; endPos = i + 1; } } System.out.println("我们测试结果:"); System.out.println("Max:" + max); System.out.println("startPos:" + startPos + ",endPos:" + (endPos - 1)); } }
运行结果:
更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。
您可能感兴趣的文章:
- Java中使用辗转相除法求最大公约数
- Java求素数和最大公约数的简单代码示例
- Java求两个正整数的最大公约数和最小公倍数
- java求最大公约数与最小公倍数的方法示例
- java实现任意四则运算表达式求值算法
- Java实现的求逆矩阵算法示例
- Java 蒙特卡洛算法求圆周率近似值实例详解
- Java求10到100000之间的水仙花数算法示例
- java实现的n*n矩阵求值及求逆矩阵算法示例
- Java实现Floyd算法求最短路径
- Java求解两个非负整数最大公约数算法【循环法与递归法】
赞 (0)