动态规划---最大和的子集

雨点打透心脏的1/2处 2022-05-23 07:47 113阅读 0赞

1、题目：

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
    Output: 6
    Explanation: [4,-1,2,1] has the largest sum = 6.

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.

2、解答：这是选和不选的问题。若第i步的值加上num\[i\]小于num\[i\]则不选，若大于num\[i\]，则选。

3、代码：

C++代码

class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            //vector<int> f(nums.size());
            //f[0] = nums[0];
            //for(int i=1;i<nums.size();i++){
             //   f[i] = max(f[i-1]+nums[i],nums[i]);
           // }
            //return *std::max_element(f.begin(),f.end());
            int ans = nums[0];
            int sum = nums[0];
            for(int i=1;i<nums.size();i++){
                sum = max(sum + nums[i],nums[i]);
                if(sum > ans)
                    ans = sum;
            }
            return ans;
        }
    };

python代码

class Solution:
        def maxSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            sum_num = nums[0]
            ans = nums[0]
            for i in range(1,len(nums)):
                sum_num = max(sum_num+nums[i],nums[i])
                if sum_num > ans:
                    ans = sum_num
            return ans

发表评论取消回复

表情：

评论列表（有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划-最大的正方形面积

题目表述 Given a 2D binary matrix filled with 0’s and 1’s, find the largest square cont...

朴灿烈づ我的快乐病毒、/ 2024年04月18日 23:46/ 0 赞/ 11 阅读

相关 leetcode 最大子序和动态规划

> 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 > 示例: > 输入: \[-2,1,-3,4,-1,2,1,-

今天药忘吃喽~/ 2023年08月17日 15:43/ 0 赞/ 59 阅读

相关动态规划c语言最大子数组之和,动态规划连续子数组的最大和

题目输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例1: 输入: num

- 日理万妓/ 2022年10月14日 15:53/ 0 赞/ 171 阅读

相关最大连续子序列和-动态规划

题目描述：给定K个整数的序列\{ N1, N2, …, NK \}，其任意连续子序列可表示为\{ Ni, Ni+1, …, Nj \}，其中 1 <= i <= j <

快来打我*/ 2022年09月23日 10:51/ 0 赞/ 144 阅读

相关 leetcode 368. Largest Divisible Subset | 368. 最大整除子集（动态规划详解）

题目 [https://leetcode.com/problems/largest-divisible-subset/][https_leetcode.com_probl

Myth丶恋晨/ 2022年08月29日 13:59/ 0 赞/ 87 阅读

相关动态规划——最大累加和

动态规划？ Time Limit: 1000MS Memory Limit: 65536KB Problem Description 动态规划作为《运筹学》的一个分支

一时失言乱红尘/ 2022年07月13日 15:27/ 0 赞/ 131 阅读

相关最大子段和动态规划实现

找到《最大子段和问题的动态规划求解》的pdf，讲解很透彻。 public class Main { public static void ma

偏执的太偏执、/ 2022年06月18日 11:08/ 0 赞/ 139 阅读

相关动态规划---最大和的子集

1、题目： Given an integer array `nums`, find the contiguous subarray (containing at least

雨点打透心脏的1/2处/ 2022年05月23日 07:47/ 0 赞/ 114 阅读

相关最大连续子序列和-动态规划

题目描述：给定K个整数的序列\{ N1, N2, …, NK \}，其任意连续子序列可表示为\{ Ni, Ni+1, …, Nj \}，其中 1 <= i <= j <

川长思鸟来/ 2022年04月11日 06:13/ 0 赞/ 209 阅读

相关动态规划——最大整除子集C++

来自LeetCode 368 描述给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 S

Bertha 。/ 2022年02月23日 03:18/ 0 赞/ 186 阅读