428-动态规划算法-最大子段和

傷城~ 2022-09-05 04:27 196阅读 0赞

## 题目如下 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

**11-4+13=20**

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        
    	int ar[] = {
         -2, 11, -4, 13, -5, -2 };
    	const int n = sizeof(ar) / sizeof(ar[0]);
    	int dp[n] = {
         0 };//状态
    	dp[0] = ar[0] < 0 ? 0 : ar[0];
    	int maxval = dp[0];
    
    	for (int i = 1; i < n; ++i)//从第一个元素开始
    	{
           //O(n)
    		dp[i] = ar[i] + dp[i - 1];//状态转移方程  子问题的最优解 =》 原问题的最优解
    		if (dp[i] < 0) 
    		{
        
    			dp[i] = 0;
    		}
    
    		if (dp[i] > maxval) 
    		{
        
    			maxval = dp[i];
    		}
    	}
    
    	cout << maxval << endl;
    
    	return 0;
    }

**运行截图如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/2c99519a94bb47d7aa174f6db4856185.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/d089cae37ff040fbb73e29fc9d1de1ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/6b712a7c7b984462abab469cae7402f8.png

发表评论取消回复

表情：

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

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

相关阅读

相关算法设计与分析——动态规划——最大字段和问题

动态规划解决问题是自底向上。原问题的规模是n个元素。这n个元素不好考虑，我们先考虑n-1个元素，这样还不好考虑，我们考虑n-2个元素，这样依次递减，最后问题规模变成

Love The Way You Lie/ 2022年10月08日 00:56/ 0 赞/ 152 阅读

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

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

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

相关 428-动态规划算法-最大子段和

题目如下 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nL

傷城~/ 2022年09月05日 04:27/ 0 赞/ 197 阅读

相关最大子段和

问题描述：给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优

雨点打透心脏的1/2处/ 2022年08月08日 06:38/ 0 赞/ 181 阅读

相关最大子段和

给定n个整数（可能包含负数）组成的序列，求该序列子段和的最大值。参考代码：常规方法1 对所有可能进行遍历，找到最终结果 include<stdio.h>

旧城等待，/ 2022年08月02日 06:44/ 0 赞/ 186 阅读

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

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

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

相关最大子矩阵（动态规划）

最大矩阵和顾名思义，就是一个矩阵和最大，例如下面的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 最终找

忘是亡心i/ 2022年06月07日 12:50/ 0 赞/ 348 阅读

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

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

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

相关最大子矩阵最大子数组动态规划

最大子矩阵最大子数组动态规划最大子矩阵问题也是动态规划中经典的一道题目（感觉自己到目前为止接触到的只是动态规划的冰山一角，区间dp、数位dp… 还是要花时间

旧城等待，/ 2022年03月15日 04:16/ 0 赞/ 314 阅读

相关最大子段和

送分题(songfen) Time Limit:1000ms Memory Limit:128MB 题目描述 LYK喜欢干一些有挑战的事，比如说求区间最大子段和。它知

港控/mmm°/ 2022年01月10日 10:53/ 0 赞/ 235 阅读