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

雨点打透心脏的1/2处 2022-05-23 07:47 174阅读 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 条评论，174人围观）

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

相关阅读

相关动态规划——416. 分割等和子集

1 题目描述给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 2 题目示例示例 1：

绝地灬酷狼/ 2023年10月08日 16:18/ 0 赞/ 42 阅读

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

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

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

相关最大正方形(动态规划)

最大正方形难度中等在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例: 输入: 1 0 1

Dear 丶/ 2023年03月12日 12:25/ 0 赞/ 9 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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