首页 > 代码库 > 求子数组的最大和及下标
求子数组的最大和及下标
转载请注明出处：http://www.cnblogs.com/wuzetiandaren/
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，故原出处已不好查到，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。下标为[2,6]。
若是时间复杂度为O(n^2),相信大家都容易解决，我用了双重循环的方法，类似于穷举法。但这里要求时间复杂度为O(n),则比较麻烦，在网上也找到不同的解决方案，其中，利用贪心算法的方式解决是相对简单的。
算法思想：
1)首先初始化子数组和的最大值max为最小负整数-(1<<31)，数组元素和sum为0,字数组的起始下标start=0和终止下标end=0。
2)从第一个元素开始循环遍历数组:
a.若相加后的sum为正，且sum>max，则max=sum；若sum<0，则sum=0。
b.否则，若sum<0，则sum=0。
算法的java实现：
1 package com.interview; 2 /** 3 * 4 * @author wjh 5 * 6 */ 7 public class _3MaxArrSum { 8 9 /**10 * @param args11 */12 public static void main(String[] args) {13 int[] a = {7,-2,-2, -2, 3, 10};//{1, -2, 3, 10, -4, 7, 2, -5};14 maxSum1(a);15 //maxSum2(a); 16 }17 18 //用二重循环 , 时间复杂度为O(n)19 private static void maxSum1(int[] a){20 int n = a.length;21 int max= -(1<<31); //用来保存最大值，初始化为最小的整数22 int sum = 0;23 int start = 0; //开始下标24 int end = 0; //结束下标 25 for(int i=0;i<n;i++){26 int temp = sum; //保存上一次的sum27 sum +=a[i];28 //如果前面选中的子数组之和已经<=0,而a[i]>0,则前面部分已经可以抛弃了,start和end从新指向当前的i29 if(temp==0&&sum>temp){ //若不求字数组的下标，则用不着这个分支 30 start=i;31 end = i;32 }33 if(sum>0&&sum>max){ //设上一个正数为a[j],当a[i]>0,并且 a[i]+ a(j,i-1] 之间的<=0的数之和大于 034 max=sum; 35 end = i; 36 }37 else if(sum<0){ //sum<0则将sum归0,若此处是else if,当形如{-2,2}的数据时第一次循环后max=sum=-2,38 sum=0; //进入第二次循环时,temp=-2;sum=0; 不会进入第一个分支,start不动,进入第二个分支时max=0;下标和结果都错误39 }40 }41 System.out.println("最大值为："+max);42 System.out.println("取得最大值时数组的起始和终止下标为: ["+start+","+end+"]"); 43 }44 /** 里面的条件分支可改为：45 * if(temp==0&&sum>temp){ //46 start=i;47 end = i;48 }49 if(sum>max){ //此时的sum肯定为正50 max=sum; 51 end = i; 52 }53 if(sum<0){ //54 sum=0; //55 }56 */57 58 //用二重循环 , 时间复杂度为O(n^2)59 private static void maxSum2(int[] a){60 int n = a.length;61 int max= -(1<<31); //用来保存最大值，初始化为最小的整数62 int start = 0; //开始下标63 int end = 0; //结束下标64 for(int i=0;i<n;i++){65 int sum = 0;66 for(int j=i;j<n;j++){67 sum += a[j];68 if(sum>max){69 max = sum;70 start = i;71 end = j;72 }73 }74 }75 System.out.println("最大值为："+max);76 System.out.println("取得最大值时数组的起始和终止下标为: ["+start+","+end+"]");77 }78 }博主白杨的文章 http://xingyunbaijunwei.blog.163.com/blog/static/7653806720122273022366/ 给了我很大的帮助，在此致谢！
求子数组的最大和及下标
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。