LeetCode_动态规划_中等_1911.最大子序列交替和

爱被打了一巴掌 2023-10-13 15:12 29阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

一个下标从 0 开始的数组的交替和定义为偶数下标处元素之和减去奇数下标处元素之和 。比方说，数组 \[4,2,5,3\] 的交替和为 (4 + 5) - (2 + 3) = 4 。

给你一个数组 nums ，请你返回 nums 中任意子序列的最大交替和（子序列的下标重新从 0 开始编号）。

一个数组的子序列是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成的数组。比方说，\[2,7,4\] 是 \[4,2,3,7,2,1,4\] 的一个子序列（加粗元素），但是 \[2,4,2\] 不是。

**示例 1：**  
输入：nums = \[4,2,5,3\]  
输出：7  
解释：最优子序列为 \[4,2,5\] ，交替和为 (4 + 5) - 2 = 7 。

**示例 2：**  
输入：nums = \[5,6,7,8\]  
输出：8  
解释：最优子序列为 \[8\] ，交替和为 8 。

**示例 3：**  
输入：nums = \[6,2,1,2,4,5\]  
输出：10  
解释：最优子序列为 \[6,1,5\] ，交替和为 (6 + 5) - 1 = 10 。

**提示：**  
1 <= nums.length <= 105  
1 <= nums\[i\] <= 105

## 2.思路 ##

（1）动态规划

相关文章：  
[LeetCode\_动态规划\_中等\_122.买卖股票的最佳时机 II][LeetCode_122._ II]

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public long maxAlternatingSum(int[] nums) {
        
            // even 和 odd 分别表示在 nums[0...i] 中选择一个子序列，并且选择的子序列的最后一个元素的下标为偶和奇数数的最大交替和
            long even = nums[0];
            long odd = 0;
            for (int i = 1; i < nums.length; i++) {
        
                even = Math.max(even, odd + nums[i]);
                odd = Math.max(odd, even - nums[i]);
            }
            return even;
        }
    }

[LeetCode_122._ II]: https://blog.csdn.net/weixin_43004044/article/details/120210000

发表评论取消回复

表情：

评论列表（有 0 条评论，29人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_动态规划_中等_1911.最大子序列交替和

目录 1.题目 2.思路 3.代码实现（Java） 1.题目一个下标从 0 开始的数组的交替和定义为偶数下标处元素之和减去奇数下标处元素之和

爱被打了一巴掌/ 2023年10月13日 15:12/ 0 赞/ 30 阅读

相关 LeetCode动态规划子序列问题——300.最长上升子序列

题目描述： [300. 最长递增子序列![icon-default.png?t=M4AD][icon-default.png_t_M4AD]https://leetcod

ゝ一世哀愁。/ 2023年10月03日 19:13/ 0 赞/ 44 阅读

相关 leetcode 最长上升子序列动态规划

> 给定一个无序的整数数组，找到其中最长上升子序列的长度。 > 示例: > 输入: \[10,9,2,5,3,7,101,18\] > 输出: 4 > 解释: 最长

梦里梦外;/ 2023年08月17日 15:43/ 0 赞/ 132 阅读

相关 leetcode 最大子序和动态规划

> 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 > 示例: > 输入: \[-2,1,-3,4,-1,2,1,-

今天药忘吃喽~/ 2023年08月17日 15:43/ 0 赞/ 123 阅读

相关动态规划---最大公共子序列（连续）

比如：“abcdkkk” 和 “baabcdadabc”，可以找到的最长的公共子序列（连续）是"abcd",所以最大公共子序列长度（连续）为 4 代码： inc

矫情吗；*/ 2023年06月25日 02:23/ 0 赞/ 29 阅读

相关最大连续子序列和-动态规划

题目描述：给定K个整数的序列\{ N1, N2, …, NK \}，其任意连续子序列可表示为\{ Ni, Ni+1, …, Nj \}，其中 1 <= i <= j <

快来打我*/ 2022年09月23日 10:51/ 0 赞/ 220 阅读

相关动态规划最大子序列和（九度1077）

练习动态规划动态规划方程：dp\[i\] = max \{dp\[i-1\] + value\[i\] , value\[i\]\} 代码： include <

忘是亡心i/ 2022年08月08日 00:59/ 0 赞/ 158 阅读

相关动态规划法-------最大连续子序列和

记得有次去索尼还有一个啥公司忘了名字，都问到了这个问题，找了下答案，特此记录一下：问题描述：数组 INT A\[\] = \{-4 , 3 ,56 , -15

红太狼/ 2022年08月05日 01:20/ 0 赞/ 189 阅读

相关动态规划（最大公共子序列）

> 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也

客官°小女子只卖身不卖艺/ 2022年06月05日 08:56/ 0 赞/ 200 阅读

相关最大连续子序列和-动态规划

题目描述：给定K个整数的序列\{ N1, N2, …, NK \}，其任意连续子序列可表示为\{ Ni, Ni+1, …, Nj \}，其中 1 <= i <= j <

川长思鸟来/ 2022年04月11日 06:13/ 0 赞/ 290 阅读