每一个你不满意的现在, 都有一个你没有努力的曾经.
G-bits Wurq
C++博客
首页
新随笔
联系
管理
<
2017年8月
>
日
一
二
三
四
五
六
30
31
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
1
2
3
4
5
6
7
8
9
统计
随笔 - 57
文章 - 7
评论 - 0
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
【C++学习记录】
(rss)
【Gsc 编译器开发】
(rss)
【LeeCode 每日N题】(50)
(rss)
【Vs 插件开发】(1)
(rss)
【成长计划】(2)
(rss)
【技术干货】(2)
(rss)
【算法详解】
(rss)
随笔档案
2017年9月 (17)
2017年8月 (15)
2017年7月 (3)
2017年6月 (18)
2017年4月 (4)
文章分类
【LLVM】(2)
(rss)
【Note】(2)
(rss)
文章档案
2017年4月 (6)
2017年3月 (1)
Blog
陈皓【酷壳】
(rss)
【C博客】MoreWindows Blog
(rss)
【博客园(sunev)】C# Socket
(rss)
陈皓【CSDN】
(rss)
子扬【博客园】
(rss)
Coder 必备技巧
.NET C# 如何监控并及时的显示另一个控制台Console的输出
(rss)
C 的 前 置 處 理 器
(rss)
关于.NET编译的目标平台(AnyCPU,x86,x64)
(rss)
C++强制类型转换的区别
(rss)
C++中的类模板详细讲述
(rss)
Git入门教程
(rss)
Gvim
(rss)
lib和dll的关系
(rss)
Makefile详解
(rss)
makefile中=、：=和+=的区别
(rss)
Microsoft Visual Studio 文件识别及其用途简述
(rss)
Vim与GCC和gdb完美组合
(rss)
控制台，终端，tty，shell等概念的区别
(rss)
在VS中添加lib库的三种方法
(rss)
正则表达式全部符号解释
(rss)
字节对齐详解
(rss)
Compiler for Wurq
vc++调用exe时，如何获取exe的输出信息
(rss)
自制编译器
(rss)
ChsLLVMDocs
(rss)
SHINING【CSDN】
(rss)
伯乐在线(解释器)
(rss)
底层虚拟机（LLVM）中间语言（IR）基本语法简介
(rss)
简单jit的实现
(rss)
用LLVM开发新语言
(rss)
搜索
最新评论
阅读排行榜
1. 【宏定义】静/动态 创建变量(392)
2. 【Vs 插件开发】清理Vs实验实例的环境(336)
3. 【成长计划 2017/8/14】第一个月的成长计划(218)
4. 【LeeCode 2017/06/12】 617. Merge Two Binary Trees (205)
5. 【编码规范】C++ 编码规范(204)
评论排行榜
1. 【宏定义】静/动态 创建变量(0)
2. 【Every Day】Fighting!!!(0)
3. 【编码规范】C++ 编码规范(0)
4. 【编程术语】(0)
5. 【LeeCode 2017/06/12】 617. Merge Two Binary Trees (0)
【LeeCode 2017/08/16】53. Maximum Subarray
动态规划:
DP2
1
//
给一串字符序列,求该序列的最大连续和
2
//
DP[i] 表示在0~i的区间内，以i结尾的最大连续子串的值。
3
//
更新DP[i]的情况有两种:
4
//
当DP[i-1]是正数，则DP[i]更新为DP[i-1]+nums[i]，可将之前的最大连续子串加上当前数值。
5
//
当DP[i-1]是负数，则DP[i]更新为nums[i],即重新划分该连续子串。
6
//
动态转义方程:
7
//
DP[i] = max(nums[i],DP[i-1] + nums[i])
8
//
=> DP[i-1]>0? DP[i-1]+nums[i] : nums[i]
9
class
Solution
10
{
11
public
:
12
int
maxSubArray(vector
<
int
>&
nums)
13
{
14
int
preSum
=
nums[
0
];
15
int
max
=
preSum;
16
for
(
int
i
=
1
; i
<
nums.size(); i
++
)
17
{
18
if
(preSum
>
0
)
19
preSum
+=
nums[i];
20
else
21
preSum
=
nums[i];
22
23
max
=
max
>
preSum
?
max : preSum;
24
}
25
return
max;
26
}
27
};
动态规划2：
DP2
1
//
给一串字符序列,求该序列的最大连续和
2
//
DP[i] 表示在0~i的区间内，最小连续子串的值。
3
//
需要先求出各个区间0~i的连续子串和,记为sum[i]。
4
//
更新DP[i]的情况有两种:
5
//
当0~i区间和sum[i]比DP[i-1]小，DP[i]则更新为sum[i]。
6
//
当0~i区间和sum[i]比DP[i-1]大，DP[i]则更新为DP[i-1]。
7
//
动态转义方程:
8
//
DP[i] = max(sum[i],DP[i-1])
9
//
=> preSum = preSum<sum[i] ? preSum:sum[i];
10
class
Solution
11
{
12
public
:
13
int
maxSubArray(vector
<
int
>&
nums)
14
{
15
if
(nums.size()
==
0
)
16
return
0
;
17
18
vector
<
int
>
sum
=
vector
<
int
>
(nums.size());
19
sum[
0
]
=
nums[
0
];
20
for
(
int
i
=
1
; i
<
nums.size(); i
++
)
21
sum[i]
=
sum[i
-
1
]
+
nums[i];
22
23
int
preSum
=
sum[
0
]
<
0
?
sum[
0
] :
0
;
24
int
max
=
sum[
0
];
25
for
(
int
i
=
1
; i
<
sum.size(); i
++
)
26
{
27
max
=
max
>
(sum[i]
-
preSum)
?
max : (sum[i]
-
preSum);
28
if
(sum[i]
<
preSum)
29
preSum
=
sum[i];
30
}
31
return
max;
32
}
33
};
posted on 2017-08-18 11:19
Wurq
阅读(196)
评论(0)
编辑
收藏
引用
所属分类:
【LeeCode 每日N题】
只有注册用户
登录
后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！
相关文章:
【LeeCode 2017/09/18】189. Rotate Array
【LeeCode 2017/09/16】172. Factorial Trailing Zeroes
【LeeCode 2017/09/15】171. Excel Sheet Column Number
【LeeCode 2017/09/14】169. Majority Element
【LeeCode 2017/09/13】168. Excel Sheet Column Title
【LeeCode 2017/09/12】167. Two Sum II - Input array is sorted
【LeeCode 2017/09/11】160. Intersection of Two Linked Lists
【LeeCode 2017/09/09】155. Min Stack
【LeeCode 2017/09/08】122. Best Time to Buy and Sell Stock II
【LeeCode 2017/09/07】141. Linked List Cycle
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理