题解 | #乘积为正数的最长连续子数组#
乘积为正数的最长连续子数组
http://www.nowcoder.com/practice/0112b9b5a09048d89309f55ea666db91
思路：动态规划
dp数组定义：
pt[i]:以第i个数结尾的乘积为正的最长子数组长度nt[i]:以第i个数结尾的乘积为负的最长子数组长度
dp数组推导式：
第 i 个数为正数时乘积有两种情况：
1.乘积为正，说明以第 i-1 个数结尾的乘积也为正：pt[i] = pt[i-1] + 1
2.乘积为负，说明以第 i-1 个数结尾的乘积也为负：nt[i] = nt[i-1] + 1(需要判断 nt[i-1]是否大于0)
第 i 个数为负数时乘积也有两种情况：
1. 乘积为正，说明以第 i-1 个数结尾的乘积为负：pt[i] = nt[i-1] + 1(需要判断 nt[i-1]是否大于0)
2. 乘积为负，说明以第 i-1 个数结尾的乘积为正：nt[i] = pt[i-1] + 1
第 i 个数为 0 时，乘积也为 0.
代码：
n = int(input()) nums = list(map(int, input().split())) pt = [0] * n nt = [0] * n pt[0] = 1 if nums[0] > 0 else 0 nt[0] = 1 if nums[0] < 0 else 0 res = 0 for i in range(1, n): if nums[i] > 0: pt[i] = pt[i-1] + 1 nt[i] = nt[i-1] + 1 if nt[i-1] > 0 else 0 elif nums[i] < 0: pt[i] = nt[i-1] + 1 if nt[i-1] > 0 else 0 nt[i] = pt[i-1] + 1 else: pt[i] = 0 nt[i] = 0 res = max(res, pt[i]) print(res)可看出每次状态都由上次的状态推导而来，且额外用res记录最大结果，故无需保存每次状态，可直接进行覆盖，无需开辟数组，优化空间，简化代码如下：
n = int(input()) nums = list(map(int, input().split())) pt = 1 if nums[0] > 0 else 0 nt = 1 if nums[0] < 0 else 0 res = 0 for i in range(1, n): if nums[i] > 0: pt += 1 nt += 1 if nt > 0 else 0 elif nums[i] < 0: tmp = pt # 这里需要注意一下先暂存pt原先的值，避免直接覆盖 pt = nt + 1 if nt > 0 else 0 nt = tmp + 1 else: pt = 0 nt = 0 res = max(res, pt) print(res)
查看3道真题和解析
投递好未来等公司10个岗位 >