动态规划——连续子数组最大和/乘积_有n个数选择其中一组连续的数使得这一组连续的数中最小值最大值和数的个数的乘积

连续子数组最大和

• 题目描述
  • 给定一个长度为 n 的数组，数组中的数为整数。
    请你选择一个非空连续子数组，使该子数组所有数之和尽可能大，子数组最小长度为1。求这个最大值。
• 输入描述
  • 第一行为一个正整数 n，代表数组的长度。1≤ n ≤2∗10⁵
    第二行为 n 个整数 ai，用空格隔开，代表数组中的每一个数。ai ≤ 10²
• 输出描述
  • 连续子数组的最大之和。
• 示例1

输入：
8
1 -2 3 10 -4 7 2 -5
输出：
18
说明：
经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
1
2
3
4
5
6
7

• 示例2

输入：
1
2
输出：
2
1
2
3
4
5

• 示例3

输入：
1
-10
输出：
-10
1
2
3
4
5

• 动态规划解题思路
  • 所得的连续子数组之和一定是第一个数和最后一个数是正数，这样才能保证连续之和最大。
  • dp[i]表示的是数组中前i个数，以第i个数结尾的连续子数组之和，即dp[i] = max(dp[i-1]+nums[i]，nums[i])。
  • 可得转移方程为：dp[i] = max(dp[i-1]+nums[i]，nums[i])。
  • 最后结果求的是dp数组中的最大值。
  • 以示例1为例：
    
• 代码

n = int(input())
nums= list(map(int, input().split()))
dp = [0]
if nums[0] > 0:
    dp[0] = arr[0]
res = nums[0]
# 算法核心部分
for i in range(1, n):
    temp = nums[i] + dp[i - 1]
    dp.append(max(temp, nums[i]))
    res = max(dp[i], res)
print(res)
1
2
3
4
5
6
7
8
9
10
11
12

• 优化
  • 可以优化空间复杂度。通过观察可以发现dp[i]依赖的是上一个值，即dp[i-1]，所以只需要定义一个pre来保存一个上一个值就可以了，免去了dp这个数组。从简单的加减法中可以发现，只有当上一个值小于0的时候，它加上当前的nums[i]的值才会小于nums[i]，于是从以上的规律，我们可以修改代码为以下：

n = int(input())
nums = list(map(int, input().split()))
pre = nums[0]
res = nums[0]
for i in range(1, n):
    if pre > 0:
        pre = pre + nums[i]
    else:
        pre = nums[i]
    res = max(pre, res)
print(res)
1
2
3
4
5
6
7
8
9
10
11

连续子数组的最大乘积

• 题目描述
  • 输入一个长度为 n 的整型数组 nums，数组中的一个或连续多个整数组成一个子数组。求所有子数 组的乘积的最大值。
    1.子数组是连续的，且最小长度为 1 ，最大长度为 n
    2.长度为 1 的子数组，乘积视为其本身，比如 [4] 的乘积为 4
    3.该题的数据保证最大的乘积不会超过 int 的范围，即不超过2³²-1
    数据范围:
    1 <= n <= 2*10⁵
    -100 <= a[i] <= 100
• 输入描述
  • 第一行输入一个正整数 n ，表示数组的长度
    第二行输入 n 个整数，表示数组中的值。
• 示例1

输入：
4
3 2 -2 4
输出：
6
说明：
子数组[3,2]的乘积为6，[3,2,-1,4]的乘积为-24，[4]的乘积为4，故返回6
1
2
3
4
5
6
7

• 示例2

输入：
3
-3 0 -2
输出：
0
说明：
因为0在中间，所有包含0的子数组的乘积都为0，另外的数都是负数，所以最大乘积的子数组为[0]，返回为0，因为子数组要求是连续的，所以[-3,-2]不是[-3,0,-2]的子数组，所以不能为6，
1
2
3
4
5
6
7

• 示例3

输入：
3
-3 2 -2
输出：
12
1
2
3
4
5

• 解题思路
  • 这题跟上一题的思路基本一致，但是值得注意的是：乘法中负数与负数相乘得到的是正数，所以每次要记录下最小的值，在每次循环时，都要将最小的值与当前遍历得到的值进行相乘。
• 代码

n = int(input())
nums = list(map(int, input().split()))
res = nums[0]
maxNum, minNum = nums[0], nums[0]
for num in nums[1:]:
    n1, n2 = num * maxNum, num * minNum
    maxNum = max(n1, n2, num)
    minNum = min(n1, n2, num)
    res = max(res, maxNum)
print(res)
1
2
3
4
5
6
7
8
9
10