好的网站设计作品,漯河公司做网站,网站交互是什么,wordpress 书籍 pdf写在前面 最近想复习一下数据结构与算法相关的内容#xff0c;找一些题来做一做。如有更好思路#xff0c;欢迎指正。 目录 写在前面一、场景描述二、具体步骤1.环境说明2.代码 写在后面 一、场景描述 最大子序和。给你一个整数数组 nums #xff0c;请你找出一个具有最大和…写在前面 最近想复习一下数据结构与算法相关的内容找一些题来做一做。如有更好思路欢迎指正。 目录 写在前面一、场景描述二、具体步骤1.环境说明2.代码 写在后面 一、场景描述 最大子序和。给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 说明子数组是数组中的一个连续部分
示例1
输入nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6示例 2
输入nums [5, 4, -1, 7, 8]
输出23二、具体步骤
1.环境说明
名称说明IntelliJ IDEA2019.2
2.代码
以下为Java版本实现
public class Lc53_maxSubArray {public static void main(String[] args) {int[] nums {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(maxSubArray(nums));}/*** 思路* 返回值是int** 求最大和的连续子数组** 动态规划* 用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」 f(i) max{ f(i−1) nums[i], nums[i]}** 动态规划和递归类似都是把大问题拆分成小问题解决。* 区别在于* 动态规划是自底向上的解决方式。通常使用迭代的方式从最小的问题开始解决然后逐步构建解决方案* 递归是自顶向下的解决方式不断调用自身来解决问题直到达到基本情况** 判断前面数的和 当前值与 当前值的大小* 如果比当前值小那么就需要重新开始子数组为什么因为题目求的是最大和的子数组加起来比当前值还小就没必要加起来了* 否则前面数的和 当前值 作为下一次数的和。 注意前面数的和 当前值不是说一直越加越大有可能会变小但是这个序列中一定存在最大值** 简答说就是通过比较将数组变成了一个一个的子数组。** 比如-2, 1, -3, 4, -1, 2, 1, -5, 4* 过程分析如下* -2, preSum -2, max -2此时序列是 -2* -2, 1舍弃-2 preSum 1, max 1此时序列是 1* 1-3 preSum -2, max 1此时序列是 1 -3* 4, 舍弃-3前面的preSum4, max4此时序列是 4* 4 -1, preSum 3 max4此时序列是4-1* 4-12preSum 5, max 5此时序列是4-12* 4-121preSum6max6此时序列是4-121* 4-121-5preSum1max6此时序列是4-121-5* 4-121-54preSum5max6此时序列是4-121-54** param nums* return*/private static int maxSubArray(int[] nums) {int max nums[0], preSum 0;for (int num : nums) {preSum Math.max(preSum num, num);max Math.max(preSum, max);}return max;}}写在后面 如果本文内容对您有价值或者有启发的话欢迎点赞、关注、评论和转发。您的反馈和陪伴将促进我们共同进步和成长。
