求连续数组子序咧的最大和
数组 最大 连续
2023-09-11 14:22:20 时间
理解,temp[i] 代表前i项的和,temp[i]的值取决于temp[i-1]的值(temp[i-1]是前 i-1项的和),试想,如果temp[i-1]<0的话,继续加的话反而会将整体值削减了,得到的状态转移方程为:temp[i] = (temp[i-1]>0?temp[i-1]:0)+a[i];
只求最大值:
// 状态转移方程为 temp[i] = (temp[i-1]>0?temp[i-1]:0)+a[i]; public static int getMaxSubSet(int[] a) { int len = a.length; int tempMax = a[0], max = a[0]; // tempMax 存储的是状态方程的temp[i-1]项和 for (int i = 1; i < len; i++) { // 循环从下标1开始,第一次循环相当于求temp[1] = (temp[0]>0?temp:0)+a[1] tempMax = (tempMax > 0 ? tempMax : 0) + a[i]; max = (max > tempMax ? max : tempMax); } return max; }
求最大值及连续子序的起始:
public static int getMax(int[] a) { int start = 0,end = 0; int len = a.length; int tempMax = a[0], max = a[0]; // tempMax 存储的是状态方程的temp[i-1]项和 for (int i = 1; i < len; i++) { // 循环从下标1开始,第一次循环相当于求temp[1] = (temp[0]>0?temp:0)+a[1] if(tempMax > 0) { tempMax += a[i]; }else { tempMax = a[i]; //从i下标重新计算 start = i; } if(tempMax > max) { max = tempMax; end = i; //记录终点下标 } } System.out.println("连续下标从"+start+"到"+end); return max; }
参考:https://blog.csdn.net/qq_24034545/article/details/82379821
相关文章
- javascript 判断变量是否是数组(Array)
- Java实现 LeetCode 215. 数组中的第K个最大元素
- Java实现最大连续乘积子数组
- Java实现最大连续乘积子数组
- Java实现最大连续乘积子数组
- Java实现最大连续乘积子数组
- leetcode - 子数组最大平均值
- (剑指Offer)面试题31:连续子数组的最大和
- 【基础入门题005】求列表(或数组)嵌套的最大深度
- linux shell带索引下标遍历数组
- 华为OD机试 - 几何平均值最大子数组(Java & JS & Python)
- Python编程语言学习:仅需一行代码将字符串化的数字数组、int数组、float数组实现之间互换(将一个字符串数组转换成整型数组)
- 【华为OD机试 2023最新 】 等和子数组最小和(C++)
- 【 华为OD机试 2023】 最大平分数组(C++ Java JavaScript Python)
- 【 华为OD机试 2023】 组装新的数组(C++ Java JavaScript Python)
- 1031. 两个非重叠子数组的最大和-构造子数组和数组遍历数组
- 剑指 Offer 42. 连续子数组的最大和-动态规划法
- 习题 5.7 找出一个二维数组中的鞍点,即该位置上的元素在该行上最大,在该列上最小(也可能没有鞍点)。
- 习题 6.8 找出一个二维数组中的鞍点,即该位置上的元素在该行上最大、在该列上最小。也可能没有鞍点。
- Leetcode 643. 子数组最大平均数 I(网友思路)
- 连续子数组的最大和
- 动态规划典型例题--连续子数组的最大和
- 二维数组中的最大联通子数组
- Go语言自学系列 | golang数组
- 算法设计--在数组中找求和最大的连续子串
- 剑指 Offer 42. 连续子数组的最大和