LeetCode例题讲解:最大子数组和
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组
是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1] 输出:1
示例 3:
输入:nums = [5,4,-1,7,8] 输出:23
首先计算任意开头和结尾,计算其中间的数值和。
int maxSubArray(int* nums, int numsSize) {
int a,b;
int sum = 0;
for(int i = a; i <= b ; i++)
{
sum += nums[i];
}
return 0;
}
之后开始for循环,计算任意两端的值,并取出最大值
int maxSubArray(int* nums, int numsSize) {
int max = 0;
for(int a = 0 ; a < numsSize ; a++)
{
for(int b = a ; b < numsSize ; b++)
{
int sum = 0;
for(int i = a; i <= b ; i++)
{
sum += nums[i];
}
if(sum > max)
max = sum;
//printf("%d %d : %d\n",a,b,sum);
}
}
return max;
}
发现若数组为-1则无法通过,需改进max初始值
int max = INT_MIN;
而后则发现超出时间限制,需要再加以改进
先简化一层
int maxSubArray(int* nums, int numsSize) {
int max = INT_MIN;
for(int a = 0 ; a < numsSize ; a++)
{
int sum = 0;
for(int b = a ; b < numsSize ; b++)
{
sum += nums[b];
if(sum > max)
max = sum;
//printf("%d %d : %d\n",a,b,sum);
}
}
return max;
}
原文地址:https://blog.csdn.net/heyijieyou1/article/details/138546485
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!