剑指offer:连续子数组的最大和

题目:例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)

动态规划: 

/**
 * @author :GY
 * @version :1.0
 * @ClassName :
 * @Description TODO
 * @date :Created in 2019/4/14 19:20
 * @description :连续子数组的最大和,下标不一定从0开始
 * 动态规划:通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
 */
public class Q30 {
    public static void main(String[] args) {
        int[] array={6,-3,-2,7,-15,1,2,2};
        int [] array1={1,-2,3,-4,5,6,-7,-8,-9,12,10};
        int[] array2={-2,-8,-1,-5,-9};
        int [] array3={1,-2,3,10,-4,7,2,-5};
        int value=0;
        //value=FindGreatestSumOfSubArray(array2);
        value=FindGreatestSumOfSubArrayTest(array);
        System.out.println(value);
    }

//    动态规划-终极版
    /*
     * value=上一个最大子数组的和
     * sum=max(sum+array[i],array[i])
     * value=max(value,sum);
    *
    * 记录上一个最大子数组的和,
    * 取sum+array[i],sum之间的最大值sum
    * 取此次的数组和与上次的数组和的最大值
    * */
    public static  int FindGreatestSumOfSubArrayTest(int[] array) {
        int sum=0;
        int value=array[0];
        for (int i=0;i<array.length;i++){
            sum=Math.max(sum+array[i],array[i]);
            value=Math.max(value,sum);
        }
        return value;
    }


//    动态规划-低级版
    /*如果sum被加上arra[i]之后。还没有array[i]大,则子序列从array[i]开始。
    * 如果sum比上一次最大和大,则更新最大值*/
    public static  int FindGreatestSumOfSubArray(int[] array) {
        if (array==null||array.length==0){
            return 0;
        }
        int sum=0;
        int value=0;
        int count=array[0];
        for (int i=0;i<array.length;i++){
            value=sum;
            sum+=array[i];
//            解决最大和的连续子数组的下标不一定是从0开始
            if(value*sum<0||sum<array[i]){
                sum=array[i];
            }
//            更换最大和
            if (count<sum){
                count=sum;
            }
        }
        return count;
    }
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:27
明天又是董事长面,啥时候是个头啊
积极向上的林同学:董事长亲自面试
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务