17.连续子数组的最大和.md

目录介绍

• 01.题目要求
• 02.问题分析
• 03.实例代码

好消息

• 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
• 链接地址：https://github.com/yangchong211/YCBlogs
• 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.题目要求

• 问题如下所示：
  • 输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
• 示例 :

  - 例如输入的数组为{1, -2, 3, 10, -4, 7, 2, -5}，那么最大的子数组为｛3, 10, -4, 7, 2}。因此输出为该子数组的和18 。
  

02.问题分析

• 解法一：举例分析数组的规律。
  • 我们试着从头到尾逐个累加示例数组中的每个数字。初始化和为0。第一步加上第一个数字1， 此时和为1。接下来第二步加上数字-2，和就变成了-1。第三步刷上数字3。我们注意到由于此前累计的和是－1 ，小于0，那如果用-1 加上3 ，得到的和是2 ， 比3 本身还小。也就是说从第一个数字开始的子数组的和会小于从第三个数字开始的子数组的和。因此我们不用考虑从第一个数字开始的子数组，之前累计的和也被抛弃。
  • 我们从第三个数字重新开始累加，此时得到的和是3 。接下来第四步加10，得到和为13 。第五步加上-4， 和为9。我们发现由于-4 是一个负数，因此累加-4 之后得到的和比原来的和还要小。因此我们要把之前得到的和13 保存下来，它有可能是最大的子数组的和。第六步加上数字7，9 加7 的结果是16，此时和比之前最大的和13 还要大， 把最大的子数组的和由13更新为16。第七步加上2，累加得到的和为18，同时我们也要更新最大子数组的和。第八步加上最后一个数字-5，由于得到的和为13 ，小于此前最大的和18，因此最终最大的子数组的和为18 ，对应的子数组是｛3, 10, -4, 7, 2｝。

03.实例代码

• 如下所示

  public class Test {
      /**
       * 输入一个整型数组，数组里有正数也有负数。数组中一个或连
       * 续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
       *
       * @param arr 输入数组
       * @return 最大的连续子数组和
       */
      public static int findGreatestSumOfSubArray(int[] arr) {
          // 参数校验
          if (arr == null || arr.length < 1) {
              throw new IllegalArgumentException("Array must contain an element");
          }
  
          // 记录最大的子数组和，开始时是最小的整数
          int max = Integer.MIN_VALUE;
          // 当前的和
          int curMax = 0;
          // 数组遍历
          for (int i : arr) {
              // 如果当前和小于等于0，就重新设置当前和
              if (curMax <= 0) {
                  curMax = i;
              }
              // 如果当前和大于0，累加当前和
              else {
                  curMax += i;
              }
  
              // 更新记录到的最在的子数组和
              if (max < curMax) {
                  max = curMax;
              }
          }
          return max;
      }
  }
  

04.测试代码

• 如下所示

  public static void test() {
  	int[] a = {1, -2, 3, 10, -4, 7, 2, -5};
  	int moreThanHalfNum = findGreatestSumOfSubArray(a);
  	System.out.print(moreThanHalfNum);
  }
  
  //输出结果：18
  

其他内容

01.关于博客汇总链接

• 1.技术博客汇总
• 2.开源项目汇总
• 3.生活博客汇总
• 4.喜马拉雅音频汇总
• 5.其他汇总

02.关于我的博客

• 我的个人站点：
• github：https://github.com/yangchong211
• 知乎：https://www.zhihu.com/people/yczbj/activities
• 简书：http://www.jianshu.com/u/b7b2c6ed9284
• csdn：http://my.csdn.net/m0_37700275
• 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
• 开源中国：https://my.oschina.net/zbj1618/blog
• 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
• 邮箱：[email protected]
• 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
• segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
• 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e