个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
25
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章求最大子数组之和的方法解析（2种可选）由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
问题描述：一个有n个元素的数组，这n个元素可以是正数也可以是负数，求最大子数组的和.
方法1：蛮力法 。
思路：最简单也是最容易想到的方法就是找出所有子数组，然后求所有子数组的和，在所有子数组的和中取最大值.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/**
* 方法1（蛮力法）：两次循环求最大子数组之和
*/
public
static
int
maxSubArray1(
int
[] a){
int
i,j;
int
ThisSum=
0
;
int
MaxSum=
0
;
for
(i =
0
; i < a.length; i++) {
ThisSum=a[i];
for
(j=i+
1
;j<a.length;j++){
ThisSum+=a[j];
if
(ThisSum>MaxSum){
MaxSum=ThisSum;
}
}
}
return
MaxSum;
}
|
方法2：优化的动态规划 。
思路：首先可以根据数组的最后一个元素a[n-1]与最大子数组的关系分为以下三种情况:
1) 最大子数组包含a[n-1]，即以a[n-1]结尾.
2) a[n-1]单独构成最大子数组.
3) 最大子数组不包含a[n-1]，那么求a[1,...,n-1]的最大子数组可以转换为求a[1,...,n-2]的最大子数组.
通过上述分析可以得出如下结论：假设已经计算出(a[0],...a[i-1])最大的一段数组和为All[i-1]，同时也计算出(a[0],...a[i-1])中包含a[i-1]的最大的一段数组和为End[i-1]， 。
则可以得出如下关系：All[i-1]=max{a[i-1],End[i-1],All[i-1]}。利用这个公式和动态规划的思想解决问题。(代码中还解决了起始位置，终止位置的问题) 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
/**
* 方法2：优化的动态规划方法
* nEnd就是通过“数组依次相加加到a[i]，然后与a[i]做比较”得来的，保存较大的。因为如果前面的数加到a[i]
* 还没有a[i]本身大，那么前面的数也就对最大子数组和没有贡献。厉害
* nAll就是记录一下之前的新得到的nEnd和自身之前谁更大
*/
public
static
int
max(
int
m,
int
n){
return
m>n?m:n;
}
public
static
int
maxSubArray2(
int
[] a){
int
nAll=a[
0
];
//有n个数字数组的最大子数组之和
int
nEnd=a[
0
];
//有n个数字数组包含最后一个元素的子数组的最大和
for
(
int
i =
1
; i < a.length; i++) {
nEnd=max(nEnd+a[i],a[i]);
nAll=max(nEnd, nAll);
}
return
nAll;
}
private
static
int
begin=
0
;
private
static
int
end=
0
;
/**
* 求出最大子数组的开始begin，结尾end，以及整个子数组
*/
public
static
int
maxSubArray3(
int
[] a){
int
maxSum=Integer.MIN_VALUE;
int
nSum=
0
;
int
nStart=
0
;
for
(
int
i =
0
; i < a.length; i++) {
if
(nSum<
0
){
nSum=a[i];
nStart=i;
}
else
{
nSum+=a[i];
}
if
(nSum>maxSum){
maxSum=nSum;
begin=nStart;
end=i;
}
}
return
maxSum;
}
|
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持我！ 。
原文链接：http://www.cnblogs.com/winorgohome/p/6038320.html 。
最后此篇关于求最大子数组之和的方法解析（2种可选）的文章就讲到这里了,如果你想了解更多关于求最大子数组之和的方法解析（2种可选）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
我一直在使用 AJAX 从我正在创建的网络服务中解析 JSON 数组时遇到问题。我的前端是一个简单的 ajax 和 jquery 组合，用于显示从我正在创建的网络服务返回的结果。 尽管知道我的数据库查
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开，visit the help center . 关闭 1
我在尝试运行 Android 应用程序时遇到问题并收到以下错误 java.lang.NoClassDefFoundError: com.parse.Parse 当我尝试运行该应用时。 最佳答案 在这
有什么办法可以防止etree在解析HTML内容时解析HTML实体吗？ html = etree.HTML('&') html.find('.//body').text 这给了我 '&' 但我想
我有一个有点疯狂的例子，但对于那些 JavaScript 函数作用域专家来说，它看起来是一个很好的练习: (function (global) { // our module number one
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题. 已关闭 8 年前。 Improve th
我需要编写一个脚本来获取链接并解析链接页面的 HTML 以提取标题和其他一些数据，例如可能是简短的描述，就像您链接到 Facebook 上的内容一样。 当用户向站点添加链接时将调用它，因此在客户端启动
在 VS Code 中本地开发时，包解析为 C:/Users//AppData/Local/Microsoft/TypeScript/3.5/node_modules/@types//index而不是
我在将 json 从 php 解析为 javascript 时遇到问题 这是我的示例代码: //function MethodAjax = function (wsFile, param) {
我在将 json 从 php 解析为 javascript 时遇到问题 这是我的示例代码: //function MethodAjax = function (wsFile, param) {
我被赋予了将一种语言“翻译”成另一种语言的工作。对于使用正则表达式的简单逐行方法来说，源代码过于灵活(复杂)。我在哪里可以了解更多关于词法分析和解析器的信息？ 最佳答案 如果你想对这个主题产生“情绪化
您好，我在解析此文本时遇到问题 { { { {[system1];1;1;0.612509325}; {[system2];1;
我正在为 adobe after effects 在 extendscript 中编写一些代码，最终变成了 javascript。 我有一个数组，我想只搜索单词“assemble”并返回整个 jc3_
我有这段代码: $(document).ready(function() { // }); 问题:FB_RequireFeatures block 外部的代码先于其内部的代码执行。因此 who
背景： netcore项目中有些服务是在通过中间件来通信的，比如orleans组件。它里面服务和客户端会指定网关和端口，我们只需要开放客户端给外界，服务端关闭端口。相当于去掉host，这样省掉了些
1.首先贴上我试验成功的代码 复制代码 代码如下: protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec)
什么是 XML？ XML 指可扩展标记语言（eXtensible Markup Language），标准通用标记语言的子集，是一种用于标记电子文件使其具有结构性的标记语言。 你可以通过本站学习 X
【PHP代码】 复制代码 代码如下: $stmt = mssql_init('P__Global_Test', $conn) or die("initialize sto
在SQL查询分析器执行以下代码就可以了。 复制代码代码如下: declare @t varchar(255),@c varchar(255) declare table_cursor curs
前言 最近练习了一些前端算法题，现在做个总结，以下题目都是个人写法，并不是标准答案，如有错误欢迎指出，有对某道题有新的想法的友友也可以在评论区发表想法，互相学习🤭 题目 题目一: 二维数组中的
我是一名优秀的程序员,十分优秀！