当前位置: 首页> 科技> 数码 > 设计公司logo的网站_互联网品牌是什么意思_网页设计免费模板_上海seo优化服务公司

设计公司logo的网站_互联网品牌是什么意思_网页设计免费模板_上海seo优化服务公司

时间:2025/7/11 8:20:55来源:https://blog.csdn.net/weixin_41554427/article/details/146883561 浏览次数:1次
设计公司logo的网站_互联网品牌是什么意思_网页设计免费模板_上海seo优化服务公司

分治法

//lSum表示[left,right]内以left为左端点的最大子段和
//rSum表示[left,right]内以right为右端点的最大字段和
//iSum表示[left,right]的区间和
int divide_conquer(int* nums,int left,int right,int *lSum,int *rSum,int *iSum){int maxSum;//表示[left,right]内的最大字段和if(left == right){*lSum = nums[left];*rSum = nums[left];*iSum = nums[left];maxSum = nums[left];return maxSum;}int mid = (left+right)/2;int lSumL,rSumL,iSumL;int maxSumL = divide_conquer(nums,left,mid,&lSumL,&rSumL,&iSumL);int lSumR,rSumR,iSumR;int maxSumR = divide_conquer(nums,mid+1,right,&lSumR,&rSumR,&iSumR);*iSum = iSumL + iSumR;*lSum = lSumL > (iSumL + lSumR) ? lSumL:(iSumL + lSumR);*rSum = rSumR > (iSumR + rSumL) ? rSumR:(iSumR + rSumL);maxSum = maxSumL > maxSumR ? maxSumL: maxSumR;if(maxSum < rSumL+lSumR)maxSum = rSumL+lSumR;return maxSum;
}int maxSubArray(int* nums, int numsSize) {int lSum,rSum,iSum;return divide_conquer(nums,0,numsSize-1,&lSum,&rSum,&iSum);
}

动态规划

第一版

int maxSubArray(int* nums, int numsSize) {if(numsSize == 1)return nums[0];int *max_sub_sum = (int*)malloc(sizeof(int)*numsSize);max_sub_sum[0] = nums[0];int max_sum = nums[0];for(int i = 1;i < numsSize;i++){max_sub_sum[i] =  max_sub_sum[i-1] + nums[i] >= nums[i] ? max_sub_sum[i-1] + nums[i]:nums[i];if(max_sub_sum[i] > max_sum)max_sum = max_sub_sum[i];}free(max_sub_sum);return max_sum;
}

分析发现,numsSize等于1的情况不用单独考虑,后面的逻辑可以涵盖这种情况:

int maxSubArray(int* nums, int numsSize) {int *max_sub_sum = (int*)malloc(sizeof(int)*numsSize);max_sub_sum[0] = nums[0];int max_sum = nums[0];for(int i = 1;i < numsSize;i++){max_sub_sum[i] =  max_sub_sum[i-1] + nums[i] >= nums[i] ? max_sub_sum[i-1] + nums[i]:nums[i];if(max_sub_sum[i] > max_sum)max_sum = max_sub_sum[i];}free(max_sub_sum);return max_sum;
}

进一步分析,发现求max_sub_sum[i]的时候,只需要用到max_sub_sum[i-1],而不需要用到max_sub_sum数组i-1前面的元素,所以可以用一个pre_max_sub_sum取代max_sub_sum数组的作用,节省内存开销。

int maxSubArray(int* nums, int numsSize) {int pre_max_sub_sum = nums[0];int max_sum = nums[0];for(int i = 1;i < numsSize;i++){pre_max_sub_sum =  pre_max_sub_sum + nums[i] >= nums[i] ? pre_max_sub_sum + nums[i]:nums[i];if(pre_max_sub_sum > max_sum)max_sum = pre_max_sub_sum;}return max_sum;
}

关键字:设计公司logo的网站_互联网品牌是什么意思_网页设计免费模板_上海seo优化服务公司

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: