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

代码一（看题解写出来）

注意：描述引用他人的，代码自己的
【剑指offer】连续子数组的最大和
典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。使用一个变量max记录最大的dp值返回即可。

    public static int fun02(int[] arr) {
        if(arr == null || arr.length == 0) return 0;
        if(arr.length == 1) return arr[1];
        int max = arr[0];
        int sum = arr[0];
        for (int i = 1;i < arr.length;i ++) {
            sum = sum > 0 ? sum + arr[i] : arr[i];
            max = max > sum ? max : sum;
        }
        return max;
    }

代码二（代码一扩展，记录左右下标）

    public static int fun03(int[] arr) {
        if(arr == null || arr.length == 0) return 0;
        if(arr.length == 1) return arr[1];
        int max = arr[0];
        int sum = arr[0];
        int left = 0;
        int right = 0;
        for (int i = 1;i < arr.length;i ++) {
            if (sum > 0) {
                sum = sum + arr[i];
            } else {
                sum = arr[i];
                left = i;
            }
            max = max > sum ? max : sum;
            right = i;
        }
        return max;
    }

代码三（自己肝出来）

    public static int fun(int[] arr) {
        if(arr == null || arr.length == 0) return 0;
        if(arr.length == 1) return arr[1];
        int max = arr[0];
        int sum = arr[0];
        //int left = 0;
        //int right = 0;
        for(int i = 1;i < arr.length;i ++) {
            int temp = sum + arr[i];
            if(temp > sum) {
                if (temp > arr[i]) {
                    sum = temp;
                } else {
                    sum = arr[i];
                    //left = i;
                }
            } else {
                max = max > sum ? max : sum;
                if(temp > arr[i]) {
                    sum = temp;
                } else {
                    sum = arr[i];
                    //left = i;
                }
            }
            //right = i;
        }

        return max > sum ? max : sum;
    }