1749. 任意子数组和的绝对值的最大值

题目描述给你一个整数数组numsnumsnums。一个子数组[numsl,numsl1,...,numsr−1,numsr][numsl, numsl1, ..., numsr-1, numsr][numsl,numsl1,...,numsr−1,numsr]的 和的绝对值 为abs(numslnumsl1...numsr−1numsr)abs(numsl numsl1 ... numsr-1 numsr)abs(numslnumsl1...numsr−1numsr)。请你找出numsnumsnums中 和的绝对值最大的任意子数组可能为空并返回该最大值。abs(x)abs(x)abs(x)定义如下如果xxx是负整数那么abs(x)−xabs(x) -xabs(x)−x。如果xxx是非负整数那么abs(x)xabs(x) xabs(x)x。示例 1输入nums [1,-3,2,3,-4]输出5解释子数组 [2,3] 和的绝对值最大为 abs(23) abs(5) 5 。示例 2输入nums [2,-5,1,-4,3,-2]输出8解释子数组 [-5,1,-4] 和的绝对值最大为 abs(-51-4) abs(-8) 8 。算法思想子数组问题用动态规划解决状态表示一般是通过经验题目要求得到所以dp[i]dp[i]dp[i]表示以iii为结尾的子数组的和取绝对值后最大的值。但是取绝对值后和最大意味着取绝对值之前该子数组和可能是最小值也可能是最大值所以一个状态表示不够要用两个状态表示f[i]f[i]f[i]表示以iii为结尾的子数组的最小和g[i]g[i]g[i]表示以iii为结尾的子数组的最大和状态转移方程以iii结尾的子数组可以划分为长度1 11的可以划分为长度1 11的对于f[i]f[i]f[i]子数组长度1 11时只有一个元素所以f[i]nums[i]f[i] nums[i]f[i]nums[i]子数组长度1 11时就是以i−1i-1i−1结尾的子数组再带上一个iii位置元素所以f[i]f[i]f[i]就是以i−1i-1i−1结尾的子数组的最小和再加上iii位置元素f[i]f[i−1]nums[i]f[i] f[i-1] nums[i]f[i]f[i−1]nums[i]综上f[i]min(nums[i],f[i−1]nums[i])f[i] min(nums[i], f[i-1] nums[i])f[i]min(nums[i],f[i−1]nums[i])对于g[i]g[i]g[i]子数组长度1 11时只有一个元素所以g[i]nums[i]g[i] nums[i]g[i]nums[i]子数组长度1 11时就是以i−1i-1i−1结尾的子数组再带上一个iii位置元素所以g[i]g[i]g[i]就是以i−1i-1i−1结尾的子数组的最大和再加上iii位置元素g[i]g[i−1]nums[i]g[i] g[i-1] nums[i]g[i]g[i−1]nums[i]综上g[i]max(nums[i],g[i−1]nums[i])g[i] max(nums[i], g[i-1] nums[i])g[i]max(nums[i],g[i−1]nums[i])初始化按照状态转移方程填f[0],g[0]f[0], g[0]f[0],g[0]时会越界所以多使用一个空间初始化f[0]0,g[0]0f[0] 0, g[0] 0f[0]0,g[0]0填表顺序从左到右填返回值f,gf, gf,g表中元素绝对值的最大值代码classSolution{public:intmaxAbsoluteSum(vectorintnums){intnnums.size();vectorintf(n1,0),g(n1,0);intret0;for(inti1;in;i){f[i]min(f[i-1]nums[i-1],nums[i-1]);g[i]max(g[i-1]nums[i-1],nums[i-1]);retmax({ret,abs(f[i]),abs(g[i])});}returnret;}};