链接：点我做题
暴力算法的思路非常简单，不是要找连续的子序列吗，那我就套两层循环，第一层循环表示当前序列是以i为开头，第二层循环j表示当前序列以j为结尾，由于是连续数组，在j的循环中，我们只要把上一轮的值加上这一轮的nums[j]就可以了，每次加完得到一个新的子序列的长度，记得用保存最大值，每次换了开头的时候，即到i循环的时候，记得sum重新置0。
代码：
class Solution {
public:
int maxSubArray(vector& nums)
{
//暴力算法
//对每个以i开头的遍历整个数组 不断保存最长长度就行
int size = nums.size();
int ret = INT_MIN;
//这类找最大值的题一开始最好把最大值设为当前类型的最小值避免出bug
int sum = 0;
for (int i = 0; i < size; i++)
{
sum = 0;
for (int j = i; j < size; j++)
{
sum += nums[j];
ret = max(sum, ret);
}
}
return ret;
}
};
时间复杂度：
O
(
N
2
)
O(N^2)
O(N2)
空间复杂度：
O
(
1
)
O(1)
O(1)
贪心算法的思想非常巧妙，想像一个以i位置为结尾的子数组，只有当它的前缀大于等于0的时候，这个前缀才是对整体值增加时有益的，如果前缀值小于0了，那应该放弃前缀，把sum重新置0，并且从当前位置重新开始算连续和sum，注意每次求得一次连续和可以用max函数存起来，每一次放弃前缀就是换一个位置重新开始计算连续和。
代码：
class Solution {
public:
int maxSubArray(vector& nums)
{
//贪心算法
//从左到右遍历 求和于sum中 并且及时维护出现过的最大值
//如果sum小于0了 说明要这段前缀对后续子数组的增加没有用了
//就可以把sum置零重新再找了
int size = nums.size();
int sum = 0;
int ret = INT_MIN;
for (int i = 0; i < size; i++)
{
if (sum < 0)
{
sum = 0;
}
sum += nums[i];
ret = max(sum, ret);
}
return ret;
}
};
时间复杂度：
O
(
N
)
O(N)
O(N)
空间复杂度：
O
(
1
)
O(1)
O(1)
动态规划关键是要建立模型，本题考虑以i为结尾的最大子序列的值f(i)，首先它有两种情况，可能就是它自己这个元素的值，可能是包含了前面的连续子序列的值与它自己的和，考虑后一种情况，任取以i-1为结尾的连续子序列，它的值一定小于等于以i-1为结尾的最大子序列的值f(i-1)，这是由f的定义决定的，那么有
f
(
i
−
1
)
+
n
u
m
s
[
i
]
>
=
任
取
的
以
i
−
1
为
结
尾
的
连
续
子
序
列
的
值
+
n
u
m
s
[
i
]
f(i-1)+nums[i] >= \任取的以i-1为结尾的连续子序列的值 + nums[i]
f(i−1)+nums[i]>=任取的以i−1为结尾的连续子序列的值+nums[i]
所以显然后一种情况时，
f
(
i
)
=
f
(
i
−
1
)
+
n
u
m
s
[
i
]
f(i)=f(i-1)+nums[i]
f(i)=f(i−1)+nums[i],综合两种情况考虑，
f
(
i
)
=
m
a
x
(
f
(
i
−
1
)
+
n
u
m
s
[
i
]
,
n
u
m
s
[
i
]
)
f(i)=max(f(i - 1) + nums[i], nums[i])
f(i)=max(f(i−1)+nums[i],nums[i])
这里的实现考虑用pre来存储f(i-1),并且初始时，f(i-1)的值显然为0，所以pre初始设置为0即可,注意用max函数保存每一轮的最大值。
代码：
class Solution {
public:
int maxSubArray(vector& nums)
{
//动态规划法
//考虑以i结尾的连续子数组的最大长度记为f[i]
//显然f[0] = nums[0]
//f[1] = max(f[0] + nums[1], nums[1])
//所以f[i] = max(f[i-1] + nums[i], nums[i])
//推理：假设已知f[i-1] 求f[i]的表达式
//以i结尾必须包含i 假设我们任意取了一个以i结尾的子串
//则其和等于到i-1的和加i的值,也可能单独等于i的值
//第一种情况时但是到i-1的值一定一定小于等于f[i - 1]
//所以f[i]=max(f[i-1]+nums[i],nums[i])
int pre = 0;//用来保存f[i-1]
int ret = nums[0];
int size = nums.size();
for (int i = 0; i < size; i++)
{
pre = max(pre + nums[i], nums[i]);
ret = max(ret, pre);
}
return ret;
}
};
时间复杂度：
O
(
N
)
O(N)
O(N)
空间复杂度：
O
(
1
)
O(1)
O(1)
这个方法属于是神奇他妈给神奇开门，神奇到家了。
首先它对一个数组区间
[
l
,
r
]
[l,r]
[l,r],定义了四个量：
i
S
u
m
−
−
区
间
里
头
所
有
元
素
的
值
l
S
u
m
−
−
以
区
间
左
端
点
为
开
头
的
子
数
组
最
大
值
r
S
u
m
−
−
以
区
间
右
端
点
为
终
点
的
子
数
组
最
大
值
m
S
u
m
−
−
区
间
最
大
子
数
组
的
值
iSum--区间里头所有元素的值 \lSum--以区间左端点为开头的子数组最大值 \rSum--以区间右端点为终点的子数组最大值 \mSum--区间最大子数组的值
iSum−−区间里头所有元素的值lSum−−以区间左端点为开头的子数组最大值rSum−−以区间右端点为终点的子数组最大值mSum−−区间最大子数组的值
并且发现，如果把区间
[
l
,
r
]
[l,r]
[l,r]以
m
=
l
+
r
2
m=frac{l+r}{2}
m=2l+r分成两个区间
[
l
,
m
]
、
[
m
+
1
,
r
]
[l,m]、[m+1,r]
[l,m]、[m+1,r],记这三个区间依次为区间1、区间2、区间3，有
i
S
u
m
1
=
i
S
u
m
2
+
i
S
u
m
3
iSum1 = iSum2 + iSum3
iSum1=iSum2+iSum3
注解：这是自然的，因为[l,r]区间是由这两个区间无重合分割的嘛；
l
S
u
m
1
=
m
a
x
(
l
S
u
m
2
,
i
S
u
m
2
+
l
S
u
m
3
)
lSum1 = max(lSum2, iSum2 + lSum3)
lSum1=max(lSum2,iSum2+lSum3)
注解：
[
l
,
r
]
[l,r]
[l,r]区间以左端点起始的最大子数组值有两种情况，一种是它这个子数组没有越过m，那它的值就等于
[
l
,
m
]
[l,m]
[l,m]区间以左端点为起始的最大子数组的值lSum2；另一种情况是这个子数组越过了m，那么拆分想想这个值就等于左边数组
[
l
,
m
]
[l,m]
[l,m]加上右边数组[m + 1, r]的以左端点为起始的最大子数组的值，即
i
S
u
m
2
+
l
S
u
m
3
iSum2 + lSum3
iSum2+lSum3.
r
S
u
m
1
=
m
a
x
(
r
S
u
m
3
,
i
S
u
m
3
+
r
S
u
m
2
)
rSum1 = max(rSum3, iSum3 + rSum2)
rSum1=max(rSum3,iSum3+rSum2)
注解：同上
m
S
u
m
1
=
m
a
x
(
m
S
u
m
1
,
m
S
u
m
2
,
r
S
u
m
2
+
l
S
u
m
3
)
mSum1 = max(mSum1, mSum2, rSum2 + lSum3)
mSum1=max(mSum1,mSum2,rSum2+lSum3)
注解：
[
l
,
r
]
[l,r]
[l,r]区间最长的子连续子数组有三种情况，整个在m左边，整个在m右边，整个正好跨过m，如果整个在m左边，那么这个值就等于区间
[
l
,
m
]
[l,m]
[l,m]最长子数组的值
m
S
u
m
2
mSum2
mSum2;如果整个在m右边，那么这个值就等于区间
[
m
+
1.
r
]
[m+1.r]
[m+1.r]的最长子数组的值
m
S
u
m
3
mSum3
mSum3;如果跨过m，那么根据拆分的方法，这个值显然等于以
[
l
,
m
]
[l,m]
[l,m]区间右端点为终点的最长子数组的值
r
S
u
m
2
rSum2
rSum2加上以
[
m
+
1
,
r
]
[m+1,r]
[m+1,r]区间左端点为起点的最长子数组的值
l
S
u
m
3
lSum3
lSum3.
并且，当区间长度被划分到1的时候，显然iSum、lSum、rSum、mSum四个值相等，都等于这个区间中的元素的值。
至此，我们给出了最小规格的任务如何完成与如何把两个区间归并回一个区间的方法，最后的结果就是总区间的mSum值，可以利用归并方法实现：
代码：
class Solution {
public:
struct State
{
int iSum;
int lSum;
int rSum;
int mSum;
};
int mymax(int x, int y, int z)
{
if (x > y)
{
if (z > x)
{
return z;
}
else
{
return x;
}
}
else
{
if (z > y)
{
return z;
}
else
{
return y;
}
}
}
State GetState(vector& a, int l, int r)
{
if (l == r)
{
int ret = a[l];
State s = {ret, ret, ret, ret};
return s;
}
int m = (l + r) / 2;
State subl = GetState(a, l, m);
State subr = GetState(a, m + 1, r);
State res = {subl.iSum + subr.iSum,
max(subl.lSum, subl.iSum + subr.lSum),
max(subr.rSum, subr.iSum + subl.rSum),
mymax(subl.mSum, subr.mSum, subl.rSum + subr.lSum)};
return res;
}
int maxSubArray(vector& nums)
{
//分治法 维护4个量
//iSum--区间里头所有元素的值
//lSum--以区间左端点为开头的子数组最大值
//rSum--以区间右端点为开头的子数组最大值
//mSum--区间最大子数组的值
//当分到区间长度=1的时候
//显然这些值都等于区间中的值
//接下来考虑恢复
//如果是[l,r]分成[l,m] [m,r] m=(l+r)/2
//记第一个为区间1 第二个区间为区间2 第三个区间为区间三
//那么iSum1 = iSum2 + iSum3
//lSum1 = max(lSum2, iSum2 + lSum3)
//rSum1 = max(rSum3, iSum3 + rSum2)
//mSum1 = max(mSum2, mSum3, rSum2 + lSum3)
State s = GetState(nums, 0, nums.size() - 1);
return s.mSum;
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）