首页 > 编程语言 > 详细

返回一个整数数组中最大子数组的和

时间:2020-02-28 20:52:25      阅读:82      评论:0      收藏:0      [点我收藏+]

要求: 输入一个整形数组,数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n) 

设计思想

  首先需要让其有数可存,设计数组,其次让其满足要求,通过限制条件,使得各个子数组求和,最后找出子数组和的最大值

出现的问题

        在编辑过程中不能很好的解决满足情况的子数组

源代码

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class number {
    public static void main(String[] args){
        List<Integer> list = new ArrayList<>();
        int sum = Integer.MIN_VALUE;
        int i,max = sum;
        Random random = new Random();
        int length = random.nextInt(5);
        for (i = 0;i < length; i++){
            list.add(random.nextBoolean()?random.nextInt(10):random.nextInt(10) * (-1));
        }
        for (i = 0;i < length; i++){
            System.out.print(list.get(i).intValue()+"   ");
        }
        System.out.println();
        for (i = 0; i < length; i++){
            if (sum < 0){
                sum = list.get(i).intValue();
            }else {
                sum += list.get(i).intValue();
            }
            if (max < sum){
                max = sum;
            }
        }
        System.out.println(max);
    }
}

总结

       自己设计思路还欠缺思考,绕了很多弯路,没有及时找到最好路径,同时还上网浏览借鉴了他人的思维,需要多思考、多动手!

返回一个整数数组中最大子数组的和

原文:https://www.cnblogs.com/PSLQYZ/p/12378726.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!