剑指offer面试题42:连续子数组的最大和(Java 实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer面试题42:连续子数组的最大和(Java 实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2079字,纯文字阅读大概需要3分钟。
内容图文
![剑指offer面试题42:连续子数组的最大和(Java 实现)](/upload/InfoBanner/zyjiaocheng/838/9f495736185f4ccb9b57152504861fd0.jpg)
题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)
例如输入的数组为{1,-2,3,10,-4,7,2,-5},和最大的子数组为{3,10,-4,7,2},因此输出为该子数组的和18。
方法一:通过枚举数组的所有子数组并求它们的和,一个长度为n的数组,子数组总共有 n(n-1)/2,计算所有子数组的和,时间复杂度为O(n²)。
方法二:通过分析数组的规律,时间复杂度为O(n)
思路:遍历一次数组,从第一个元素开始累加数组,需要判断当前和,如果当前和小于等于0,就保存当前和的最大值,从下一个元素开始累加;如果当前和大于0,直接累加后面的元素即可,然后再次判断当前和。
可以定义一个 greatSum 来保存当前和的最大值,需要注意的是要避免数组输入无效返回的0和累积数组最大值为0冲突了。
public class test_forty_two {
boolean invalidInput = false;
public int FindGreatestSumOfSubArray(int[] array){
if (array == null || array.length == 0){
invalidInput = true; //表示这是输入无效输入输出的0
return 0;
}
int greatestSum = array[0]; //用来保存当前的最大值
int currentSum = 0; //表示当前的和
for (int i=0; i < array.length; i++){
if (currentSum <= 0){
//当前和小于等于0,保存当前的最大值
currentSum = array[i];
} else {
//当前和大于0,接着累加后面的元素
currentSum = currentSum + array[i];
}
if (currentSum > greatestSum){
greatestSum = currentSum;
}
}
return greatestSum;
}
}
方法三:利用递归转动态规划的思想
这个公式的意义:当以第i-1个数字结尾的子数组中所有的数字的和小于0时,如果把这个负数与第i个数累加,得到的结果比第i个数字本身还要小,所以这种情况下以第i个数字结尾的子数组就是第i个数字本身。如果以第i-1个数字结尾的子数组中所有的数字的和大于0,与第i个数字累加就得到以第i个数字结尾的子数组中所有的数字的和。
思路:
- F(i):以array[i]为末尾元素的子数组的和的最大值
F(i)=max(F(i-1)+array[i] , array[i]) - result:所有子数组的和的最大值
result = max(result,F(i))
//方法三:利用动态规划
public int FindGreatestSumOfSubArray(int[] array){
int max = array[0]; //表示以i结尾的子数组和的最大值
int result = array[0]; //所有子数组和的最大值
for (int i=1; i<array.length; i++){
max = Math.max(max + array[i], array[i]);
result = Math.max(result, max);
}
return result;
}
内容总结
以上是互联网集市为您收集整理的剑指offer面试题42:连续子数组的最大和(Java 实现)全部内容,希望文章能够帮你解决剑指offer面试题42:连续子数组的最大和(Java 实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。