专栏首页Mybatis学习Day2-2 leetcode 53. Maximum Subarray

Day2-2 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.

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;   
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode-53-Maximum-Subarray

    最长子序列,又是一个动态规划的问题,关于动态规划,我们最主要的是要维护DP数组,这个问题以前还有点不理解,感觉主要的还是思想,只要知道这是一个动态规划的问题,解...

    小二三不乌
  • Leetcode 53 Maximum Subarray

    Find the contiguous subarray within an array (containing at least one number) w...

    triplebee
  • leetcode: 53. Maximum Subarray

    JNingWei
  • LeetCode-53-Maximum Subarray

    Find the contiguous subarray within an array (containing at least one number) wh...

    欠扁的小篮子
  • Leetcode 53. Maximum Subarray

    Find the contiguous subarray within an array (containing at least one number) wh...

    xindoo
  • LeetCode 53. Maximum Subarray

    ShenduCC
  • 、Maximum Product Subarray

    Find the contiguous subarray within an array (containing at least one number) wh...

    Tyan
  • 【Code】关关的刷题日记22——Leetcode 53. Maximum Subarray

    关小刷刷题 22——Leetcode 53. Maximum Subarray 题目 Find the contiguous subarray within a...

    WZEARW
  • Array - 53. Maximum Subarray

    Given an integer array nums, find the contiguous subarray (containing at least o...

    用户5705150
  • Leetcode#53.Maximum Subarray(最大子序和)

    题目描述 给定一个序列(至少含有 1 个数),从该序列中寻找一个连续的子序列,使得子序列的和最大。 例如,给定序列 [-2,1,-3,4,-1,2,1,-5,4...

    武培轩
  • 【Leet Code】53. Maximum Subarray

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • LeetCode Weekly Contest 41解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 【leetcode刷题】T15-最大子数组和

    今天分享leetcode第15篇文章,也是leetcode第53题—最大子数组和(Maximum Subarray)

    木又AI帮
  • leetcode-53-Maximum Subarray(动态规划详解)

    chenjx85
  • Leetcode: Maximum Subarray

    题目: Find the contiguous subarray within an array (containing at least one num...

    卡尔曼和玻尔兹曼谁曼
  • 【leetcode】高频题目整理_数组篇( High Frequency Problems, Array )

    截止至今LeetCode题目总量已经有1582题,估计将来每年平均增长300题左右,大部分人肯定是刷不完的,所以得有选择地刷LeetCode。

    嵌入式与Linux那些事
  • Leetcode: Maximum Product Subarray

    题目: Find the contiguous subarray within an array (containing at least one num...

    卡尔曼和玻尔兹曼谁曼
  • LeetCode 0053 - Maximum Subarray

    Find the contiguous subarray within an array (containing at least one number) wh...

    Reck Zhang
  • LeetCode <dp>53&121&122. Maximum Subarray & Best Time to Buy and Sell Stock

    Given an integer array nums, find the contiguous subarray (containing at least o...

    大学里的混子

扫码关注云+社区

领取腾讯云代金券