来源:http://zhedahht.blog.163.com/blog/static/254111742007219147591/
题目:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。
解决思路:
如果前几项数值累加的结果为负,则可以将这几项排除,因为负数累加后肯定会使总值减少。因此算法分别从左往后和从右往左计算相邻两个数的累加和,当大于零时继续累加,小于零时将之前的累加值清零,从后一个数字开始重新计算。当左右两边指针相遇时,将两边汇总值累加,既为最终结果。
package maxchildarray;
/**
* 子数组的最大和
* @author DHC
*
*/
public class MaxChildArray {
public static void main(String[] args) {
// 初始数组
int[] intArray = {1, -2, 3, 10, -4, 7, 2, -5};
int left = 0; // 从左边开始计算
int leftTemp = 0; // 左边现在指向的位置
int leftSum = 0; // 左边的总和
// 右边变量,同上
int right = intArray.length - 1;
int rightTemp = intArray.length - 1;
int rightSum = 0;
// 最终总和
int sum = 0;
while(true) {
// 从左往右计算,每次往后移动一位
if (leftSum + intArray[leftTemp] <= 0) {
leftTemp++;
left = leftTemp;
leftSum = 0;
} else {
leftSum += intArray[leftTemp];
leftTemp++;
}
// 从右往左计算,每次往前移动一位
if (rightSum + intArray[rightTemp] <= 0) {
rightTemp--;
right = rightTemp;
rightSum = 0;
} else {
rightSum += intArray[rightTemp];
rightTemp--;
}
// 前后相遇时进行相应处理
if (rightTemp - leftTemp == -2) {
sum = leftSum + rightSum - intArray[rightTemp];
break;
} else if (rightTemp - leftTemp == -1) {
sum = leftSum + rightSum;
break;
}
}
System.out.print("The Max Child Array is : ");
for (int i = left; i <= right; i++) {
System.out.print(intArray[i] + " ,");
}
System.out.println("\nSummery is " + sum);
}
}
练习心得:
其实算法有些时候并没有想象中的这么困难,只要自己静下心来,仔细思考内在的联系应该会有思路的。
另外感觉有了思路后用程序实现过程中会遇到很多细节的问题,这就更要想清楚了。
此算法还有另外一个思路,就是仍然从左边开始遍历,在这个过程中记录一个当前子数组的最大值,前几项小于零时则刷新所有数据,从后面一个数重新开始,当发现累加结构大于记录的最大值时,则替换,最后比较完后,记录的最大值就为真实的最大值。这种算法,只用从左边开始遍历数组,而且避免了两边同时遍历相遇时的一些处理,应该说比上面代码实现的算法更加简单,http://zhedahht.blog.163.com/blog/static/254111742007219147591/,这篇博文用C实现了这个简洁的算法。
分享到:
相关推荐
主要介绍了Java获得一个数组的指定长度排列组合算法,结合实例形式分析了java排列组合相关数组遍历、运算操作技巧,需要的朋友可以参考下
超光驱(c)2010-2011 Adam Ierymenko [ ] 在 BSD 许可下获得许可 ( ) Hyperdrive 是一个简单的 Java 库,用于创建由任意维数(2d、3d、4d、5d 等)索引的快速数组。 它对科学计算很有用。 运行 HyperdriveTester 进行...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
最大子数组问题Kadane算法的一些微小实现,以各种语言(C,C ++,python,Java)解决了最大子数组问题。 它从标准输入(即从命令行或文本文件)获取数组。
无论您是初学者还是有经验的Java开发者,通过学习这个算法,您将获得一个强大的搜索工具,有助于在大型有序数据集中快速查找元素。 二分查找是一种高效的搜索算法,特别适用于有序数组。在这个教程中,我们将深入...
通过鼠标点击来获取一个目的地,然后方块自动寻路并到达目的地,提供了Keylistener借口和Runnable接口,可进行相关扩展。
节点流和处理流 Java IO 的核心类 File Java IO 流对象 字节流对象InputStream OutputStream 字符流对象Reader Writer 字节流与字符流的转换新潮的 NIO 缓冲区(Buffer)通道(Channel) 示例:文件拷贝案例 BIO 和 NIO ...
获取数组中缺少的连续值算法,欢迎交流学习。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥...
Java数据结构和算法中文第二版(1) Java数据结构和算法中文第二版(2) 【内容简介】 本书可帮助读者: 通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择...
2、使用java NIO读取被嵌入的文件,将其转换为byte数组,需要特别指出的是原生方法得到是byte类型的数组,但是算法实现需要更加精细的操作,所以还需要对得到的byte数组进行进一步的转换封装,将其转换成形如10101...
排序算法Java开发和测试以下排序算法。 按气泡排序贝壳分类按插入排序按混合排序按土堆排序快速分类每个提交都与标记为的博客帖子相关联。 在每个帖子中都说明了排序算法。 我们首先创建一个抽象的Algorithm类,其中...
Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥...
通过由基于JAVA的演示所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择正确的算法 利用数据结构和算法为现实世界的处理过程建模 了解不同的数据结构的优势和弱点,考虑如何利用...
但是内层循环的结束条件i,这里一定要-1,原因很简单,因为在内层循环中分表使用i和i+1作为索引获取数组的元素,就要保证i和i+1都不能超出数组的索引范围,即i推导出i最后的-i只是为了提高效率,因为每趟排序都会确定一个...
文件加密解密算法(Java源码) java,file,算法,加密解密,java源码 package com.crypto.encrypt; import java.security.SecureRandom; import java.io.*; import javax.crypto.spec.DESKeySpec; import javax.crypto...
getMaxElem.java 获取数组中的最大元素 incCapicity.java 演示StingBuffer的容量增长 SortDemo.java 排序示例 travelTwoDime.java 遍历二维数组 traversing.java 遍历一维数组 useStrBuf.java 使用...
用于印度TeenPatti的带鬼牌的算法,通过牌查表获得牌型和大小。算法由texas_algorithm修改得来。测试玩玩 * 运行TestUtil.Main ## 生成表玩玩 * 运行 TeenPattiAlgorithmUtil.Main # 查表算法 查表算法,给定任意3...
Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥...
Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对(keyPair)、如何保存公钥的字节数组、保存私钥到文件privateKey.dat、如何用Java对象序列化保存私钥...