Day2-2 leetcode 53. Maximum Subarray
Day2-2 leetcode 53. Maximum Subarray
Albert_xiong
发布于 2021-06-21 17:56:21
发布于 2021-06-21 17:56:21
文章被收录于专栏：Mybatis学习
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
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.
计算出一个数组中的最大和的子列，子列必须连续
在这里插入图片描述
方法一：三层循环嵌套（在leetcode上提交会时间太长不符合要求） 1、要选择一个起点（一个for循环遍历数组中的所有元素，均可以作为起点） 2、选择一个结束点（这个点最小都是起始点的值，结束点和起始点重合） 3、选择好起始点和结束点之后，对这里面的数组元素进行求和，选出最大值的sum 时间复杂度不满足要求！！！！！
int max = INT_MIN;//其中表示最小的值
int maxSubArray(int* nums, int numsSize)
{
int max = INT_MIN;
//选择一个起始点
for(int i=0;i<numsSize;i++)
{
//选择一个结束点
for(int j=i;j<numsSize;j++)
{
int sum = 0;
for(int k=i;k<=j;k++)
{
sum = sum+nums[k];
}
if(sum>max)
{
max = sum;
}
}
}
return max;
}
在这里插入图片描述
在这里插入图片描述
方法二：缩减为两层嵌套 1、要选择一个起点（一个for循环遍历数组中的所有元素，均可以作为起点） 2、选择一个结束点（这个点最小都是起始点的值，结束点和起始点重合） 3、将第三层循环改变一下：
在这里插入图片描述
在这一层里比如说i=0，j=0 1 2 3 4 5 … 这一层， sum = sum +nums[j]每一次 都累加，然后再找出这一层的最大值，循环完这一层，再将sum置0，再进行比较…依次下去 找出最大值
int maxSubArray(int* nums, int numsSize)
{
int max = INT_MIN;
//选择一个起始点
for(int i=0;i<numsSize;i++)
{
int sum = 0;
//选择一个结束点
for(int j=i;j<numsSize;j++)
{
sum = sum + nums[j];
if(sum>max)
{
max = sum;
}
}
}
return max;
}
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/12/10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
