来源: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 语言中的数组和集合操作,掌握了 Java 中的数组声明、初始化、索引访问、遍历等操作,并使用冒泡排序算法将数组元素排序。同时,我们还学习了 Java 中的输入输出操作和异常处理。
10. **数组在算法和数据结构中的应用** 数组是许多复杂数据结构(如栈、队列、图、树等)的基础。许多算法也依赖于数组,例如快速排序、归并排序、二分查找等。 学习Java数组是理解Java基础的重要一步,掌握数组的...
在Java编程中,处理两个数组的交集是常见的数据处理任务,这通常涉及到集合操作或者算法的应用。交集是指两个数组中都存在的元素组成的集合。本文将深入探讨如何使用不同的方法来找出两个数组的交集,并提供相关的...
在这个文档中,主要涉及了Java数组的声明、创建、初始化、赋值、输出、累加和计算、最大值查找以及冒泡排序等核心概念。 1. **数组的声明与创建**: - `int[] arr;` 这是声明一个整型数组的例子。 - `int[] arr =...
2. 最大子数组和:寻找数组中连续子数组的最大和,Kadane's算法可以在一次遍历中解决,时间复杂度为O(n)。 3. 翻转数组:给定一个数组,反转数组中的元素。可以通过两个指针从两端向中间遍历并交换元素实现。 4. ...
在Java编程语言中,二维数组是一种特殊的数组...总之,理解和掌握Java中的二维数组是进行复杂数据结构处理和算法实现的基础,对于提升编程能力至关重要。通过学习和实践,我们可以灵活运用二维数组来解决各种实际问题。
在处理数组时,经常需要找出数组中的最大值和最小值,这对于数据分析、算法实现或者简单的数学计算都至关重要。本详细教程将指导你如何通过源代码在Java中实现这一功能。 首先,我们从基础开始。一个数组在Java中...
Java数组堆栈可以应用于各种场景,例如,解析表达式、实现递归算法、缓存数据等。同时,ArrayStack类也可以作为其他数据结构的基础,例如,链表、树等。 结论 Java数组堆栈是基于数组的堆栈数据结构,提供了基本的...
Java中的数组可以是一维的也可以是多维的,而了解数组的声明和初始化、如何获取数组长度以及如何输出数组元素的值是操作数组的关键。通过编写程序来输出一维数组和二维数组的长度与内容,可以加深对数组结构和数组...
Java一维数组是Java编程语言中的基础数据...掌握这些概念是进一步学习高级数据结构和算法的基础,也是编写高效Java代码的关键。在实际编程中,灵活运用数组可以解决许多问题,因此深入理解并熟练运用数组是非常重要的。
总结起来,Java中的数组操作是编程的基础,掌握如何定义、初始化、访问、修改、遍历、排序和置换数组元素对于编写高效的Java程序至关重要。通过熟练运用这些技巧,开发者可以更好地解决实际问题,并提高代码的可读性...
在编程领域,数组排列组合问题是一个经典的问题,它涉及到算法设计和数据结构的理解。这个问题的主要目标是从给定的n个数组中找出所有的可能排列组合。Java作为一种强大的编程语言,提供了丰富的工具和方法来解决...
在Java编程中,"从n个数组中取出所有的组合"是一个经典的算法问题,涉及到排列组合的概念。这通常可以通过回溯法或递归策略来解决。下面我们将深入探讨这个主题。 首先,我们需要理解“排列”与“组合”的概念。...
4-6 数组和排序算法章节练习 5-0 抽象和封装 5-1 面向过程的设计思想 5-2 面向对象的设计思想 5-3 抽象 5-4 封装 5-5 属性 5-6 方法的定义 5-7 this关键字 5-8 javaBean 5-9 包 package 5-10 抽象和封装章节练习 6-0...
在Java编程中,字符串数组和大数据运算经常被用于复杂的数据处理和计算场景。在这个特定的示例中,我们要实现一个程序来计算表达式 (1+2)(1+2^2)*(1+2^3)*...*(1+2^100) 的结果。这个表达式涉及到指数运算和乘法,这...
### Java数组中的查找:基础知识与实现细节 在Java编程中,数组是一种常用的数据结构,用于存储固定大小的同类型元素序列。对数组进行查找是基本且频繁的操作之一,特别是对于初学者而言,掌握如何在数组中查找特定...
在实际编程中,数组不仅用于存储和操作数据,还常用于算法实现,如排序、查找等。了解和掌握数组的声明、初始化、引用、赋值以及遍历是Java编程的基础,也是进一步学习面向对象编程、继承、多态和异常处理等高级概念...
总的来说,从Java的int数组中获取最大值是一个基础但重要的算法,通过遍历数组并比较元素,我们可以有效地找出数组中的最大数。这个方法不仅适用于整型数组,也可以应用于其他类型的数据,只需相应地调整数据类型...
本节我们将深入探讨Java中的数组操作,并重点讲解选择排序算法。 数组在Java中的定义与初始化: 在Java中,数组可以通过以下方式声明和初始化: ```java int[] array = new int[5]; // 声明一个包含5个元素的整型...