題目描述
給定一個(gè)整數(shù)數(shù)組 nums 氮惯，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）注竿，返回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6初狰。
解題思路
先求出數(shù)組中的最大值設(shè)為max，后面的連續(xù)的數(shù)相加與max相比互例，如比max小奢入，則從下一個(gè)數(shù)重新開始相加計(jì)算
#include<stdio.h>
int maxSubArray(int* nums, int numsSize)
{
int i,j,max,temp;
max = temp = 0;
max = nums[0];
//找出數(shù)組中最大值
for(i=1;i<numsSize;i++)
{
if(nums[i]>max)
max = nums[i];
}
printf("%d\n",max);
//相加比較找最大值
for(i=0;i<numsSize;i++)
{//兩兩相加進(jìn)行比較
temp += nums[i];
max = temp<max ? max:temp;
printf("%d,%d,%d ",temp,max,nums[i]);
temp = temp< 0 ? 0:temp;
printf("%d\n",temp);
}
return max;
}
int main()
{
int sum,len;
int nums[]={-2,1,-3,4,-1,2,1,-5,4};
len = 9;
sum = maxSubArray(nums, len);
printf("%d\n",sum);
return 0;
}
image.png
