首页 > 其他分享 >计算给定整数数组中,第i个元素表示从第i个位置开始按摩到最后一个位置能够获得的最大收益。

计算给定整数数组中,第i个元素表示从第i个位置开始按摩到最后一个位置能够获得的最大收益。

时间:2024-04-04 12:23:00浏览次数:27  
标签:dp1 nums dp0 int 位置 给定 数组 Vector

算法:计算给定整数数组中,第i个元素表示从第i个位置开始按摩到最后一个位置能够获得的最大收益。

解题思路:使用动态规划方法解决。

代码示例:

  public int massage(Vector<Integer> nums) {
        int n = nums.size();
        if (n < 0) {
            return 0;
        }
        int dp0 = 0, dp1 = nums.get(0);
        for (int i = 1; i < n; i++) {
            int temp = dp0;
            int tp0 = Math.max(dp0, dp1);
            int tp1 = temp + nums.get(i);
            dp0 = tp0;
            dp1 = tp1;
        }
        return Math.max(dp0, dp1);
    }

潜在问题与风险提醒
数组大小检查:你的代码中对nums的大小进行了检查(n < 0),这是一个好的做法。但是,应该检查的是n <= 0,因为如果数组为空(n == 0),你的方法也应当有明确的行为表现(在这种情况下,返回0是合理的)。
使用Vector类:在现代Java编程中,通常不推荐使用Vector类,因为它对每个操作都进行同步,这可能会引入不必要的性能开销。除非你需要确保线程安全,否则建议使用ArrayList来代替。
异常处理:你的方法没有对可能的异常进行处理,例如,如果传递给方法的nums为null,则在调用nums.size()时将会抛出NullPointerException。建议在方法开始时添加对nums的非空检查。
代码优化方向
代码可读性:增加方法的注释是个好习惯,但是可以进一步优化。例如,更详细地解释动态规划的状态转移方程,以及dp0和dp1分别代表的含义,可以帮助其他开发者更快地理解代码逻辑。
变量命名:在你的代码中,变量dp0和dp1用于表示两种状态,虽然在动态规划的上下文中这是常见的,但对于不熟悉动态规划的开发者来说可能有些晦涩。考虑使用更具描述性的命名,比如currentMax和nextMax,或在注释中加以说明。
性能优化:当前的实现在遍历数组时,多次调用了nums.get(i)方法,这实际上是对索引访问的重复操作。考虑到Vector是基于索引访问的,可以将当前元素的值先存储在一个局部变量中,然后使用这个局部变量,以减少对get方法的调用次数。
边界条件处理:在你的代码中,对于数组大小的检查只考虑了n < 0的情况,如前所述,还应该考虑n == 0的情况。在处理边界条件时,确保代码的行为符合预期是很重要的。
使用泛型:虽然在这个特定的例子中没有直接相关,但通常建议在使用集合时指定泛型类型,以增强类型安全性和代码可读性。例如,使用Vector<Integer>而不是简单的Vector。

以下是优化后的代码:

/**
 * 计算给定整数数组中,第i个元素表示从第i个位置开始按摩到最后一个位置能够获得的最大收益。
 * 使用动态规划方法解决。
 * @param nums 整数数组,表示每个位置的按摩收益。
 * @return 返回最大收益。
 */
public int massage(ArrayList<Integer> nums) {
    // 检查输入数组是否为空或null
    if (nums == null || nums.size() <= 0) {
        return 0;
    }
    
    int n = nums.size();
    int currentMax = 0; // 当前位置的最大收益
    int nextMax = nums.get(0); // 下一个位置的最大收益

    for (int i = 1; i < n; i++) {
        int temp = currentMax;
        // 状态转移方程,计算下一个位置的最大收益
        currentMax = Math.max(currentMax, nextMax);
        // 对当前元素进行计算,更新下一个位置的最大收益
        nextMax = temp + nums.get(i);
    }
    
    // 返回两个状态中的最大值,即整个数组中的最大收益
    return Math.max(currentMax, nextMax);
}

 

标签:dp1,nums,dp0,int,位置,给定,数组,Vector
From: https://www.cnblogs.com/bwcx1375/p/18114062

相关文章

  • 4.7 数组的读取和写入,type指令和一些杂项
    4.7数组的读取和写入,type指令和一些杂项可以通过wordptr将db转为dw,然后按照dw的方式去存储数据1.段名也可以把其地址赋给变量assumecs:codesg,ds:data,ss:stackdatasegmentdb12,34dw12,34db'helloworld'dataendsstacksegmentdb10d......
  • 柔性数组
    柔性数组(FlexibleArrayMember)是C语言中的一种特性,允许在结构体的末尾定义一个数组,但是这个数组的大小可以在运行时确定。柔性数组通常用于动态分配内存,特别是在需要保存可变数量元素的情况下非常有用。一般来说,柔性数组的定义方式如下所示:structflex_array{intleng......
  • 在排序数组中查找元素的第一个和最后一个位置
    34.在排序数组中查找元素的第一个和最后一个位置-力扣(LeetCode)题目描述给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target,返回 [-1,-1]。你必须设计并实现时间复杂......
  • 翻转数组
    publicclassexample{ publicstaticvoidmain(String[]args){ intarr[]={1,2,3,4,5,6}; inttemp=0; intlen=arr.length; for(inti=0;i<len/2;i++){ temp=arr[len-1-i]; arr[len-1-i]=arr[i]; arr[i]=tem......
  • python如何对二维数组排序
    在Python中对二维数组进行排序是一个常见的需求,可以通过多种方式实现。在本博客中,我们将讨论几种常见的方法来对二维数组进行排序。首先,我们可以使用Python的内置函数sorted()对二维数组进行排序。sorted()函数可以接受一个key参数,通过指定key参数来指定排序的方式。下面是......
  • JS实现检查给定时间范围是否在每天的某个时间段内
    //解析时间字符串,返回对应的分钟数functionparseTime(timeStr){const[hours,minutes]=timeStr.split(':').map(num=>parseInt(num));returnhours*60+minutes;}//解析时间字符串,返回对应的Date对象functionparseTimeString(timeStr){const......
  • 2024.3.8力扣每日一题——找出美丽数组的最小和
    2024.3.8题目来源我的题解方法一数学题目来源力扣每日一题;题序:2834我的题解方法一数学经过分析,在target之前,取小于等于target/2的正整数才能使得和最小,并且满足条件3。时间复杂度:O(n)空间复杂度:O(n)publicintminimumPossibleSum(intn,inttarget)......
  • Transformer模型-Positional Encoding位置编码的简明介绍
    今天介绍transformer模型的positionalencoding 位置编码背景位置编码用于为序列中的每个标记或单词提供一个相对位置。在阅读句子时,每个单词都依赖于其周围的单词。例如,有些单词在不同的上下文中具有不同的含义,因此模型应该能够理解这些变化以及每个单词所依赖的上下文。......
  • PTA:7-116 点与圆的位置关系
    作者 zzz单位 重庆科技大学在平面直角坐标系中,给定一个圆的圆心坐标Ox,Oy以及半径R,再给定一个点的坐标Px,Py,请判断这个点与圆的位置关系。输入格式:先输入三个正整数,分别代表圆心的横纵坐标Ox,Oy和半径R。在输入两个正整数,分别代表给定点的横纵坐标Px,Py。输入的所有数......
  • 详解volatile 关键字的作用,Java 中能创建 volatile 数组吗
    该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点面试官:volatile关键字的作用可见性:当一个线程修改了volatile变量的值,这个新值对于其他线程是立即可见的。这是因为在多线程环境下,线程在修改volatile变量的值时......