每日一题--连续子数组的最大值
程序员文章站
2022-04-11 19:01:07
...
思想:动态规划
用递归的方式分析动态规划问题,但编码时常常使用循环来解决
解题思路
设置两个变量:一个保存最大值,一个保存当前遍历到i的最大值(用动态规划,公式见下方)
代码:
/**动态规划
* 问题:输入一个整型数组,有正数也有负数。数组中连续几个数字为一个子数组,求所有子数组的最大值
* 输入:{1,-2,3,10,-4,7,2,-5},最大的子数组为{3,10,-4,7,3,-5}
* 输出:18
* Created by lxq on 2017/9/3.
*/
public class Problem3 {
public static void main(String[] args){
Problem3 problem3 = new Problem3();
int[] array = {1,-2,3,10,-4,7,2,-5};
int result = problem3.getGreatestSubArray(array);
System.out.println(result);
}
public int getGreatestSubArray(int[] array){
if(array==null)
return 0;
int currentSum = 0;
int greatestSum = 0;
//用循环的方式
for(int i=0;i<array.length;i++){
if(currentSum<=0){
currentSum = array[i];
}else {
currentSum +=array[i];
}
if(currentSum>greatestSum){
greatestSum = currentSum;
}
}
return greatestSum;
}
}
上一篇: java-子序列最大值
推荐阅读
-
SQL Server 2008 R2——查找最小nIndex,nIndex存在而nIndex+1不存在 求最小连续数组中的最大值
-
Python语言描述连续子数组的最大和
-
剑指 Offer 42. 连续子数组的最大和——从这题开始学习动态规划
-
程序员代码面试指南 python实现(第一章 栈和队列 :最大值减去最小值小于或等于num的子数组数量)
-
给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
-
连续子数组的最大和
-
连续子数组的最大和
-
面试题 42. 连续子数组的最大和 Python3 动态规划
-
剑指Offer之连续子数组的最大和
-
连续子数组的最大和