Java练习题——(二)最大子序列交替和

发布于 2023-07-11  305 次阅读


——From tyhty

题目描述:

一个下标从 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

解题思路:

该题目的本质其实就是创建出一个最终结果最大的子序列数组。而由于事先我们并不道nums[i]元素是否被选中,即存在:选种该元素和不选中该元素两种情况。而在选中之后又存在两种情况:作为偶数下标加入子序列则子序列长度为奇数;作为奇数下标加入子序列则子序列长度为偶数。因此,在本题中我们需要对长度为偶数和长度为奇数的子序列最大交替和做讨论。

我们假设存在两个数组变量dp[i][0]表示0-i范围内的构造长度为偶数的子序列的最大交替和,dp[i][1]表示0-i范围内的构造长度为奇数的子序列的最大交替和。

那么我们的最终的最大交替和的结果就是dp[i][0]和dp[i][1]中的最大值。

接下来,我们又对两种情况做分别讨论:

首先是dp[i][0]的情况,如果其长度为偶数,那么存在两种可能的情况,第一种是dp[i][0]=dp[i-1][0],第二种是dp[i][0]=dp[i-1][1]+nums[i]。因为我们可以知道,在上一次的dp[i-1][0],其长度为偶数位,故而当dp[i][0]不添加元素时,其就继承dp[i-1][0],大小长度不变;而如果添加元素,其前一轮的长度就必须是奇数长,故而必须选择上一轮的dp[i-1][1],所以其就可能是上一轮的奇数位+这一轮添加的元素。而在偶数长的情况下,其最大交替值就是这两种情况下的最大值。

同理,在dp[i][1]的情况下,也是存在两种情况,第一种是继承前一轮的奇数长的值,第二种是选择前一轮的偶数长+这一轮添加的元素。

而每一轮就会得出一个该轮最大交替值(max(even,odd))。

下面是图解:

image.png

如上图所示,进行一轮遍历就可以得到结果。

源代码:

public long maxAlternatingSum(int[] nums) {
        int len = nums.length;
        //even代表序列的第一个元素只含一个元素,odd表示子序列首先为空没有元素。
        long even=nums[0];//奇数长度的子序列
        long odd=0;//偶数长度的子序列
        //even和odd中的最大值就是最优子序列的结果。
        long sum = nums[0];
        long bigger = 0;
        for(int i = 1;i<len;i++)
        {
            even = Math.max(even,odd+nums[i]);
            odd = Math.max(odd,even-nums[i]);
            bigger = Math.max(even,odd);
            sum = Math.max(bigger,sum);
        }

        return sum;
    }

分析:

在本题中,通过上述方法我们看到,通过简单的一轮数据遍历就能找到,遍历为i次。故而时间复杂度为O(n),空间复杂度为O(1)。


一花一世界,一叶一菩提。