本文实例讲述了Java实现求子数组和的最大值算法。分享给大家供大家参考，具体如下：
一般C和C++在算法实现中使用较多，下面我们通过java语言实现算法，更有亲切感。
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
实现代码：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
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("快网idc测试结果：");
System.out.println("Max:" + max);
System.out.println("startPos:" + startPos + ",endPos:" + (endPos - 1));
}
}
|
运行结果：
希望本文所述对大家java程序设计有所帮助。
原文链接：http://blog.csdn.net/yayun0516/article/details/47323489
相关文章
猜你喜欢
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持？ 2025-06-10
- 64M VPS建站：如何选择最适合的网站建设平台？ 2025-06-10
- ASP.NET本地开发时常见的配置错误及解决方法？ 2025-06-10
- ASP.NET自助建站系统的数据库备份与恢复操作指南 2025-06-10
