描述

给定一个长度为 的数组，数组中的数为整数。
请你选择一个非空连续子数组，使该子数组所有数之和尽可能大。求这个最大值。

示例1

输入：
3
3 -4 5

输出：
5

说明：
选择 [5] 这个子数组即可。

示例2

输入：
3
4 -3 5

输出：
6

说明：
选择 [4,-3,5] 这个子数组。

思路

其实这道题不难理解，大家想一下，对于某一个元素，该位置上最打的子数组和 = max（该元素的值， 该元素的值 + 前一个位置对应的最大子数组和），因为 前一个位置对应的最大子数组和 可能为负数，如果为负数，那么之前的就应该舍弃掉，以当前元素为新的最大子数组和。

AC 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入长度
        long n = Long.parseLong(sc.nextLine());
        // 输入数组
        String[] arrStr = sc.nextLine().split(" ");
        long[] arr = new long[arrStr.length];
        for (int i = 0; i < arrStr.length; i++) {
            arr[i] = Long.parseLong(arrStr[i]);
        }

        long run = run(arr.length, arr);
        System.out.println(run);
    }

    public static long run(int n, long[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }

        // 前一个元素下标对应最大的子数组和
        long cur = arr[0];
        // 总的最大子数组和
        long res = arr[0];
        for (int i = 1; i < arr.length; i ++) {
            // cur = 当前元素 和 当前元素 + 前一位元素下标对应最大子数组和 中的最大值
            cur = Math.max(arr[i], arr[i] + cur);
            // 更新 res
            res = Math.max(res, cur);
        }
        return res;
    }
}

• 时间复杂度：O(N)， N 为数组长度，因为要遍历一遍
• 空间复杂度：O(1)， 没有使用额外空间。