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

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

2021-04-05 12:40yayun0516 Java教程

这篇文章主要介绍了Java实现求子数组和的最大值算法,涉及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));

									    }

									}