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

Java实现求子数组和的最大值算法示例

程序员文章站 2023-12-25 16:43:51
本文实例讲述了java实现求子数组和的最大值算法。分享给大家供大家参考,具体如下: 一般c和c++在算法实现中使用较多,下面我们通过java语言实现算法,更有亲切感。...

本文实例讲述了java实现求子数组和的最大值算法。分享给大家供大家参考,具体如下:

一般c和c++在算法实现中使用较多,下面我们通过java语言实现算法,更有亲切感。

题目:

输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。

实现代码:

package arrdemo;
public class maxsub {
    public static void main(string[] args) {
        // todo 自动生成的方法存根
        findmaxsubarysum1();
    }
    public static void findmaxsubarysum1() {
        // sum为子数组的和
        int sum = 0;
        // max为子数组的最大和
        int max = 0;
        // 最大子数组的起始位置
        int startpos = 0;
        // 最大子数组的结束位置
        int endpos = 0;
        int[] array = { -1, 2, -3, 12, -5, -1, 9, -2 };
        for (int i = 0; i < array.length; i++) {
            sum += array[i];// 求和
            if (sum < 0) {// 如果当前求得总和为负数的话,就将其清零,并且开始位置从下一个位置开始
                sum = 0;
                startpos = i + 1;
            }
            if (sum > max) {// 如果求得总和大于之前的最大值的话,就将sum赋值给max,同时记录最后的位置
                max = sum;
                endpos = i + 1;
            }
        }
        system.out.println("测试结果:");
        system.out.println("max:" + max);
        system.out.println("startpos:" + startpos + ",endpos:" + (endpos - 1));
    }
}

运行结果:

Java实现求子数组和的最大值算法示例

更多关于java算法相关内容感兴趣的读者可查看本站专题:《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总

希望本文所述对大家java程序设计有所帮助。

上一篇:

下一篇: