LeetCode-53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

分析

这道题一开始的时候太大意了,忽略了很多的问题,当然这个

错误分析

错误的理解题目的意思是求数组中的最大的和,因而答案就有点微妙了。

#include "stdio.h"
int maxSubArray(int* nums, int numsSize) {
    int temp=0;
    int sum=0;
    if(numsSize==1)
    {
        return nums[0];
    }
    else
        {
        for(int i=0;i<numsSize;i++)
        {
            for(int j=i;j<numsSize;j++)
            {
                if(nums[i]<nums[j])
                    temp=nums[i];
                    nums[i]=nums[j];
                    nums[j]=temp;
            }
        } //end for
              for(int i=0;i<numsSize;i++)
              {
                  if(nums[i]>0)
                  {
                      sum+=nums[i];
                  }
              } //end for
        return sum;
        }
}
int main(){
    int nums[]=[-2,1,-3,4,-1,2,1,-5,4];
    int numsSize=9;
    printf("%d",maxSubArray(nums,numsSize));
    return 0;
}

正确的题解

int maxSubArray(int* nums, int numsSize) {
       int i,j;
            if(numsSize<=0)
                return 0;

            int sum=0;
            int realSum=nums[0];

            for(i = 0;i<numsSize;i++){
                sum+=nums[i];
//                if  sum is less than zero
                if(sum<0){
                    realSum = (realSum>sum)?realSum:sum;
                    sum = 0;
                    continue;
                }
//                sum>0 判断当前数值和sum的大小,如果realSum 大则选择realSum 否则想下一个延伸
                realSum = (realSum>sum)?realSum:sum;
            }
            return realSum;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注