banner
ekko

ekko's blog

时间不在于你拥有多少,而在于你怎样使用
github
xbox
email

最大子序和

描述#

给定一个整数数组 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;
}
加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。