描述#
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O (n) 的解法，尝试使用更为精妙的分治法求解。
思路#
- 找出整个数组的最大元素，若不大于 0，则直接返回该数
- 最大元素大于 0，则说明最大子序和也一定大于 0，遍历数组中的数，正数则作为子数组第一个往后加计算和，若和小于 0 则重新找子数组，若和大于最大值则更新
int maxSubArray(int* nums, int numsSize){
int now_val = 0,max_val = nums[0];
for(int i=0;i<numsSize;i++)//找出最大的元素
if(nums[i] > max_val)
max_val = nums[i];
if(max_val <= 0)//最大元素不大于零直接返回
return max_val;
//已经确定max_value一定大于零
for(int i=0;i<numsSize-1;i++) {
if(nums[i] > 0) {
for(int j=i+1,now_val=nums[i];j<numsSize;j++) {
now_val += nums[j];
if(now_val <= 0)
break;
if(now_val > max_val)
max_val = now_val;
}
}
}
return max_val;
}