题解 | #连续子数组最大和#

连续子数组最大和

http://www.nowcoder.com/practice/1718131e719746e9a56fb29c40cc8f95

注意题眼,连续,然后是求子数组最大和,通过滑动窗口的方式可以对比找到连续子数组最大和。

public class SumTest {
    public static void main(String[] args) {
        // AB36-连续子数组最大和 (解法1)
        Scanner scanner = new Scanner(System.in);
        // 输入数组长度
        long aLong = Long.parseLong(scanner.nextLine());
        // 输入数组
        String[] arrStr = scanner.nextLine().split(" ");
        long[] arr = new long[arrStr.length];
        // 将输入的数遍历存放到long数组中
        for (int i = 0; i < arrStr.length; i++) {
            arr[i] = Long.parseLong(arrStr[i]);
        }
        long subSum = maxArray1(arr.length, arr);
        System.out.println("连续子数组最大和为:" + subSum);

    }

    private static long maxArray1(int length, long[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        // 前一个元素下标对应的最大子数组之和
        long pre = arr[0];
        // 总的最大子数组之和
        long sum = arr[0];
        for (int i = 1; i < length; i++) {
            // pre = 当前元素 和 当前元素+ 前一位元素下标对应最大子数组和中的 最大值
            pre = Math.max(arr[i], arr[i] + pre);
            // 更新最大子数组之和
            sum = Math.max(pre, sum);
        }
        return sum;
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-15 17:24
点赞 评论 收藏
分享
zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
05-27 14:57
西北大学 golang
强大的社畜在走神:27届真不用急,可以搞点项目、竞赛再沉淀沉淀,我大二的时候还在天天打游戏呢
投递华为等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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