假设现在有一个数组 int[] arr = [5, -5, -4, 9, -9, 4, -5, -9, 8]，要获取这个这个数组中连续子元素的最大和

第一种方法，暴力获取，我们可以通过两次循环来获取

1.定义两个变量 thisSum 和 endSum，分别表示当前子元素的和，最终获取的最大连续子元素和

2.进行第一次循环，每次循环开始时将thisSum重新赋值，即thisSum = 0;

3.在第一次循环中再次进行循环，本次循环操作对数组中的子元素进行累加操作

4.判断thisSum是否大于endSum，若大于则对endSum重新进行赋值操作，即endSum = thisSum;

5.返回endSum

 

代码如下：

复制代码 
public static int violenceCalc(int[] arr) {
        int thisSum, endSum = arr[0];
        for (int i = 0; i < arr.length; i++) {
            thisSum = 0;
            for (int j = i; j < arr.length; j++) {
                thisSum += arr[j];
                if (thisSum > endSum) {
                    endSum = thisSum;
                }
            }
        }
        return endSum;      
}
复制代码

上述代码经过两次循环操作，时间复杂度为O(n^2)

若想提高代码的执行效率，我们可以采用另外一种写法

 

第二种方法，我们可以通过在线计算来获取

1.定义两个变量分为当前子元素和 thisSum ,最大连续子元素和 endSum

2.对数组遍历，进行累加操作

3.判断当前 thisSum 是否大于 endSum，若大于则对 endSum重新赋值

4.判断当前 thisSum 是否大于0，如果当前 thisSum < 0 的话，再次使用其进行累加操作的话我们认为他只会减小连续子元素的和，所以对其重新赋值，即thisSum = 0;

5.返回结果 endSum

 

代码如下：

复制代码 
public static int onlineCalc(int[] arr) {
        //创建两个变量用来记录值，一个用来记录当前累加得到的值，一个用来记录最终得到的值
        int thisSum = 0, endSum = arr[0];
        //遍历进行累加操作
        for (Integer integer : arr) {
            //进行对元素进行累加操作
            thisSum += integer;
            //如果累加后的结果大于当前记录的最终结果值，则对最终记录值重新赋值
            if (thisSum > endSum) {
                endSum = thisSum;
            } else if (thisSum < 0) {
                //如果当前累加值小于0的话，累加操作会减小值，则将当前累加的结果清零重新进行累加操作
                thisSum = 0;
            }
        }
        return endSum;
    }
复制代码

这种方法只是用了一次循环，时间复杂度为O(n)

两种方法都可以实现，但是相对于第一种方法，第二种方法的代码执行效率更高一些

原文地址：http://www.cnblogs.com/ccclyang/p/16810847.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性