专栏首页专知【Code】关关的刷题日记22——Leetcode 53. Maximum Subarray

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

关小刷刷题 22——Leetcode 53. Maximum Subarray

题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6

题目的意思是找出连续子序列的最大和。

思路

思路:典型的动态规划问题,以第i个数为结尾的连续子序列最大和sum[i] 是 (sum[i-1]+nums[i], nums[i])中较大的数。不断更新re用来存前i个数中和最大的连续子序列的和。时间复杂度O(n).

class Solution {public:
    int maxSubArray(vector<int>& nums) {
        int sum=nums[0], re=nums[0];
        for(int i=1; i<nums.size();i++)
        {
            sum=max(sum+nums[i],nums[i]);
            re=max(sum,re);
        }
        return re;
    }};

照顾好自己的身体,控制好自己的情绪,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

本文分享自微信公众号 - 专知(Quan_Zhuanzhi),作者:关关

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-11-01

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Leetcode 303】关关的刷题日记67–Leetcode 303 Range Sum Query – Immutable

    关关的刷题日记67 – Leetcode 303 Range Sum Query – Immutable 题目 Given an integer array n...

    WZEARW
  • 【LeetCode 136】 关关的刷题日记32 Single Number

    关关的刷题日记32 – Leetcode 136. Single Number 题目 Given an array of integers, every ele...

    WZEARW
  • 关关的刷题日记05 —— Leetcode 219. Contains Duplicate II

    关小刷刷题06 – Leetcode 219. Contains Duplicate II 题目 Given an array of integers and ...

    WZEARW
  • LeetCode 494. 目标和(DFS+DP)

    给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符...

    Michael阿明
  • 最大子序列和(leetcode)

    euclid
  • LeetCode268. 缺失数字

    mathor
  • Leetcode 1365. 有多少小于当前数字的数字(C语言)

    给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。

    Kindear
  • 力扣560——和为K的子数组

    给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

    健程之道
  • 回溯算法:求子集问题!

    题目地址:https://leetcode-cn.com/problems/subsets/

    代码随想录
  • 十大经典排序算法整理汇总(附代码)

    本文整理并总结了十大经典的排序算法(冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、计数排序、基数排序、桶排序、堆排序)的时间复杂度、空间复杂度等性...

    godweiyang

扫码关注云+社区

领取腾讯云代金券