首页 > 代码库 > 寻找最大子串
寻找最大子串
题目:从一个数组中寻找一个连续子数组,使其中元素之和最大,给出该和值。
例如:数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]和最大的子串是[4, -1, 2, 1],其和为6。
分析:
将数组从中间切分,中间元素属于左边,则最大子串为下面三种情况之一:
子串仅包含左边元素;
子串仅包含右边元素;
子串同时包含左边和右边的元素;
代码:
// JavaScript solution function findMaxSubArray(a, begin, end) { if(begin >= end) return a[begin]; // 边界判断 var middle = Math.floor((begin + end) / 2); var leftRtn = findMaxSubArray(a, begin, middle); // 递归查找左边最大值 var rightRtn = findMaxSubArray(a, middle+1, end); // 递归查找右边最大值 // 查找同时包含左右元素的最大值 var leftMax = a[middle]; var rightMax = a[middle+1]; var tempSum = 0; for(var i = middle; i >= begin; --i) { tempSum += a[i]; if(tempSum > leftMax) leftMax = tempSum; } tempSum = 0; for(var i = middle + 1; i <= end; ++i) { tempSum += a[i]; if(tempSum > rightMax) rightMax = tempSum; } return Math.max(leftMax + rightMax, leftRtn, rightRtn); } // Test case var testArray = [-2, 1, -3, 4, -1, 2, 1, -5, 4]; console.log(findMaxSubArray(testArray, 0, testArray.length - 1)); // Output ==> 6
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。