动态规划之最大连续子序列和
问题描述：
给定一个整数序列，a0, a1, a2, …… , an（项可以为负数），求其中最大的子序列和。如果所有整数都是负数，那么最大子序列和为0；
动态规划解法
这是最常见的方法了，简单有效，好理解。
状态转移方程：sum[i] = max{sum[i-1]+a[i],a[i]}. (sum[i]记录以a[i]为子序列末端的最大序子列连续和)
其实完全可以不用开数组，累计sum直到sum + a < a，把sum赋值为a，更新最大值就行了。
//动态规划算法
int MaxSum(int n)
{
int sum=0,b=0;
for(int i=0;i<n;i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;
}
return sum;
}
Python
def max_sum(n, a):
sum_val = 0
b = 0
for i in range(n):
if b > 0:
b += a[i]
else:
b = a[i]
if b > sum_val:
sum_val = b
return sum_val
C++: 找最大的对应的左右区间。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
scanf("%d", &n);
vector<int> v(n);
int leftindex = 0, rightindex = n - 1, sum = -1, temp = 0, tempindex = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &v[i]);
temp = temp + v[i];
if (temp < 0) {
temp = 0;
tempindex = i + 1;
} else if (temp > sum) {
sum = temp;
leftindex = tempindex;
rightindex = i;
}
}
if (sum < 0) sum = 0;
printf("%d %d %d", sum, v[leftindex], v[rightindex]);
return 0;
}
动态规划之最大连续子序列乘积
与之类似
class Solution {
public:
int maxProduct(vector<int>& nums) {
int a = nums[0], b = nums[0];
int res = a;
for (int i = 1; i < nums.size(); i++) {
int a1 = a;
a = max(a*nums[i], max(nums[i], b*nums[i]));
b = min(b*nums[i], min(nums[i], a1*nums[i]));
res = max(a, res);
cout << a << " " << b << " " << res << endl;
}
return res;
}
};
动态规划之最长递增子序列
用f[i]记录位置i的数结尾的序列长度,初始化皆为1
//java:
public class Test {
public static void main(String[] args) {
int[] num = new int[]{1,4,7,2,5,8,3,6,9};
int[] f = new int[num.length];
for (int i = 0;i < num.length;i++) {
f[i] = 1;
}
int max = f[0];
for (int i = 1;i < num.length;i++) {
for (int j = 0;j < i;j++) {
//更新条件，1是有序，2是长度能变长
if (num[i] >= num[j] && f[i] < f[j] + 1) {
f[i] = f[j] + 1;
if (f[i] > max) {
max = f[i];//更新最长的长度
}
}
}
}
System.out.println(max);
}
}
使用一个辅助空间B数组。 Bi存储Dp值为i的最小的数字。（有多个位置，以这些位置为结尾的LIS长度都为i， 则这些数字中最小的一个存在Bi中） 则B数组严格递增。且下标表示LIS长度，也是严格递增，可以在B数组中进行二分查找。
对于每个位置i，我们要找，所有小于Ai, 且Dp值最大的那个，然后把Dp(i+1)更新为A(i)。这个操作在B数组中二分查找。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
d = []
for n in nums:
if not d or n > d[-1]:
d.append(n)
else:
l, r = 0, len(d) - 1
loc = r
while l <= r:
mid = (l + r) // 2
if d[mid] >= n:
loc = mid
r = mid - 1
else:
l = mid + 1
d[loc] = n
return len(d)
动态规划之最长非递减子序列
最长非递减子序列。
差异在于递增还是非递减。
# 最长非递减子序列
def LIS(self, nums: List[int]):
g = []
for x in nums:
import bisect
j = bisect.bisect_right(g, x)
if j == len(g):
g.append(x)
else:
g[j] = x
return len(nums) - len(g)
最大非递减子序列和
O(nlogn)
线段树维护前面的最大子序列和。每次找小于当前元素的最大子序列和。
MOD = int(1e9 + 7)
INF = float('inf')
import sortedcontainers
import bisect
import heapq
class Solution:
def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
# len = 12
d = []
n = len(nums)
l = INF
r = float('-inf')
for i in range(n):
if nums[i] > 0:
# l = min(l, nums[i] - i)
# r = max(r, nums[i] - i)
d.append((nums[i] - i, nums[i]))
if not d:
return max(nums)
seg = SegmentTree(SegOpCollect.Collect_Max, SegOpUpdate.Update_SetVal, default_val=0)
diff2index = {}
x = sorted(set([v[0] for v in d]))
# 离散化
for v in x:
diff2index[v] = len(diff2index)
# print(d)
# print(diff2index)
l, r = 0, len(diff2index)
# len = 12
seg.build(left=l, right=r)
for v in d:
t = seg.query_interval(l, diff2index[v[0]])
seg.set_point(diff2index[v[0]], t + v[1])
return seg.query_interval(l, r)