首页 > 代码库 > 求子数组之和的最大值——编程之美 2.14 扩展问题 正确实现
求子数组之和的最大值——编程之美 2.14 扩展问题 正确实现
使用动态规划求最大子数字和：s[i]表示data[i~n-1]以元素i开始的最大子数组和，a[i]表示data[i~n-1]中的最大子数组和 ；s[i]=max(s[i+1]+data[i], data[i]);a[i]=max(a[i+1], s[i]); 由于数组s,a递推的时候，都只用到数组的前一个变量，所以可以用滚动数组节省空间。
扩展问题：
1) 如果数组首尾相连，即允许找到一组数字(A[i],···,A[n-1], A[0],···, A[j])，请使其和最大，怎么办？（书中答案错误，可以使用旋转数组的方法，时间复杂度n2，本文参考别人的想法，实现的算法复杂度为n）
2) 如果题目要求返回最大子数组的位置，算法应该如何改变？还能保持O(N)的复杂度么？
具体实现及思路如下：
1 #include <cstdio> 2 3 /* 4 使用动态规划求最大子数字和： 5 s[i]表示data[i~n-1]以元素i开始的最大子数组和，a[i]表示data[i~n-1]中的最大子数组和 ； 6 s[i]=max(s[i+1]+data[i], data[i]); 7 a[i]=max(a[i+1], s[i]); 8 9 由于数组s,a递推的时候，都只用到数组的前一个变量，所以可以用滚动数组节省空间。 10 */ 11 int maxSum(int data[], int n) 12 { 13 int s = data[n-1]; 14 int a = data[n-1]; 15 for(int i = n-2; i>=0; i--) 16 { 17 if(s<0) 18 s=0; 19 s+=data[i]; 20 if(s > a) 21 a = s; 22 } 23 return a; 24 } 25 26 /* 27 如果要求返回最大子数组和的位置，如何处理？ 28 使用curEnd记录当前最大字数组和的结束位置， 29 当s（以元素i开始的最大子数组和） 小于零时，更新curEnd字数组末端标记， 30 当a（当前的最大子数组和）发生变化时，更新最大字数组的标记Start，End 31 */ 32 int maxSum2(int data[], int n,int &start, int &end) 33 { 34 int s = data[n-1]; 35 int a = data[n-1]; 36 int curEnd = n-1; 37 38 start = end = n-1; 39 for(int i = n-2; i>=0; i--) 40 { 41 if(s<0) 42 { 43 s=0; 44 curEnd = i; 45 } 46 s+=data[i]; 47 if(s > a) 48 { 49 a = s; 50 start = i; 51 end = curEnd; 52 } 53 54 } 55 return a; 56 } 57 58 /* 59 如果数组arr[0],…,arr[n-1]首尾相邻，也就是允许找到一段数字arr[i],…,arr[n-1],arr[0],…,a[j]，使其和最大，该如何？ 60 编程之美的答案的思路有问题，详见： http://www.ahathinking.com/archives/120.html 61 参考该文算法，可知在允许数组跨界（首尾相邻）时，最大子数组的和为下面的最大值 62 Maxsum={ 原问题的最大子数组和；数组所有元素总值-最小子数组和 } 63 */ 64 int maxSum3(int data[], int n) 65 { 66 int maxs = data[n-1]; 67 int maxa = data[n-1]; 68 int sumAll = data[n-1]; 69 70 int mins = data[n-1]; 71 int mina = data[n-1]; 72 73 for(int i = n-2; i>=0; i--) 74 { 75 sumAll+=data[i]; 76 if(maxs<0) 77 maxs=0; 78 maxs+=data[i]; 79 if(maxs > maxa) 80 maxa = maxs; 81 82 if(mins>0) 83 mins=0; 84 mins+=data[i]; 85 if(mins < mina) 86 mina = mins; 87 } 88 int maxa2 = sumAll-mina; 89 return maxa>maxa2?maxa:maxa2; 90 } 91 92 93 int main() 94 { 95 /* 96 int d[]={ 97 -4,-5,-6,-1,-5,-9 98 };*/ 99 int d[]={100 8,-10,60,3,-1,-6101 };102 int s,e;103 int res = maxSum3(d,6);104 printf("%d\n",res);105 }
求子数组之和的最大值——编程之美 2.14 扩展问题 正确实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。