欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

每日一题--连续子数组的最大值

程序员文章站 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;
    }
}