首页 > 代码库 > [LeetCode系列]最大连续子列递归求解分析
[LeetCode系列]最大连续子列递归求解分析
本文部分参考Discuss: LeetCode.
步骤1. 选择数组的中间元素. 最大子序列有两种可能: 包含此元素/不包含.
步骤2.
步骤2.1 如果最大子序列不包含中间元素, 就对左右子序列进行步骤1.
步骤2.2 如果最大子序列包含, 则结果很简单, 就是左子列的最大后缀子列(即包含左子列最后一个元素--中间元素)加上右子列的最大前缀子列(即包含右子列第一个元素--中间元素)
步骤3. 返回三者中的最大值(左子列最大值, 右子列最大值, 二者拼接最大值).
1 class Solution { 2 public: 3 int maxSubArray(int A[], int n) { 4 // IMPORTANT: Please reset any member data you declared, as 5 // the same Solution instance will be reused for each test case. 6 if(n==0) return 0; 7 return maxSubArrayHelperFunction(A,0,n-1); 8 } 9 10 int maxSubArrayHelperFunction(int A[], int left, int right) {11 if(right == left) return A[left];12 int middle = (left+right)/2;13 int leftans = maxSubArrayHelperFunction(A, left, middle);14 int rightans = maxSubArrayHelperFunction(A, middle+1, right);15 int leftmax = A[middle];16 int rightmax = A[middle+1];17 int temp = 0;18 for(int i=middle;i>=left;i--) {19 temp += A[i];20 if(temp > leftmax) leftmax = temp;21 }22 temp = 0;23 for(int i=middle+1;i<=right;i++) {24 temp += A[i];25 if(temp > rightmax) rightmax = temp;26 }27 return max(max(leftans, rightans),leftmax+rightmax);28 }29 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。