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

例如，当(a1,a2, ……a7,a8)=(1,-3, 7,8,-4,12, -10,6)时，最大子段和为：
在这里插入图片描述

算法分析：
在这里插入图片描述
在这里插入图片描述

计算最大子段和的动态规划算法

#define NUM 1001
int a[NUM];
int MaxSum(int n)
{
	int sum=0; 
	int b=0;
	for (int i=1;i<=n;i++)
	{
		if (b>0) b+=a[i]; else b=a[i];
		if (b>sum) sum=b;
	}
	return sum;
}

计算最大子段和的动态规划算法的最优解

在这里插入图片描述

#define NUM 1001
int a[NUM];
int MaxSum(int n, int &besti, int &bestj)
{
　　int sum=0; 
　　int b=0;
　　int begin = 0;
　　for (int i=1;　i<=n;　i++)
　　{
	if (b>0)　 b+=a[i]; 
	else {b=a[i];　begin = i;}
 	if (b>sum) //得到新的最优值时，更新最优解
	{
	　　sum = b; 
	　　besti = begin; 
	　　bestj = i;
	}
　　}
　　return sum;
}

在这里插入图片描述

# 算法 # c++ # 动态规划
Logo
天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

avatar 天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

avatar 天工造物局

Bokeh 3.2.0 版本全解析：新 glyph 体系、WebGL 增强与交互工具升级

Bokeh 是 Python 生态中面向浏览器的交互式数据可视化库。本篇文章围绕 Bokeh ``3.2.0``（2023 年 6 月发布的 minor milestone）展开，系统梳理该版本引入的七项核心变更：Python 3.8 支持终止、``Axis.axis_label_orientation`` 轴标签方向控制、服务器资源自定义 host/port、``HSpan``/``VSpan`

avatar 天工造物局