version at: 2022-03-29

/**
1. 如果以i结尾的子数组划分, 可以从前面的子数组推到过来, 所以可以用DP
2. dp
    2.1 状态定义: f[i] 是以i结尾的字串的和的最大值
    2.2 状态计算: 以i划分为3种情况:
        2.2.1 f[i-1] < 0, 说明继承前面的子列表也不会更大了, 所以重新开始 f[i] = nums[i]
        2.2.2 否则扩展后的子列表一定要比只有nums[i]大                  f[i] = nums[i] + f[i-1];
    2.3 每个f[i]都被前一个更新, 初始状态特判, 所以不用初始化f,  结果为MAX(f[~])
*/

class Solution {
    public int maxSubArray(int[] nums) {
        int[] f = new int[nums.length];

        for (int i = 0 ; i < nums.length ; i++) {
            f[i] = nums[i] + ( i == 0 || f[i-1] < 0 ? 0 : f[i-1]);
        }

        return Arrays.stream(f).max().getAsInt();
    }
}

version at: 2020-01-26

/**
1. 因为数字有正有负, 加正数会更大,加负数会更小, 所以累加和的最小收益是0, 累加到<0后  重新开始

2. 初值问题: result = Integer.MIN_VALUE;
3. 指针边界问题

4. 为什么这么做是对的? 
4.1 按暴力做法, 搜索空间为所有可能的子串, 
    在从左到右遍历的过程中, 可以根据 "和的正负" 在连续子串中可以分为4种情况:
    4.1.1 连续串的前一段是正数和, 后一段为负数和: 答案必定在正数和区间内, 后一段被跳过
    4.1.2 连续串的前一段是负数和, 后一段为正数和: 前一段被跳过, 答案必定在负数和区间内
    4.1.3 连续串都是负数和: 都被跳过, 取最小的负数
    4.1.4 连续串都是正数和: 答案必定会被遍历到
*/

/**
1. 状态定义：f[i]以i结尾的子段的和的最大值,  同时满足"无后效性" 和 "最优子结构"
2. 状态计算：以最后一个位置i 划分两种情况:
2.1 把i接到前面的一个数组上: f[i-i] + nums[i]
2.2 i独立出来: nums[i]
维护这两种情况的最大值

3. 边界：f[~] = 0
4. 因为只依赖前一个数, 所以可以滚动求, 节省空间


*/
class Solution {
    public int maxSubArray(int[] nums) {
        return dynamicProgramming(nums);
        // return doublePoint(nums);
    }
    public int dynamicProgramming(int[] nums){
        int maxV = nums[0], result = nums[0];
        for (int i = 1; i < nums.length ; i++){
            maxV = Math.max(nums[i], maxV + nums[i]);
            result = Math.max(result, maxV);
        }
        return result;
    }

    public int doublePoint(int[] nums){
        int result = Integer.MIN_VALUE;
        int total = 0;
        int i = 0; 
        int j = 0;
        int n = nums.length;
        while (i < n && j < n){
            if (total < 0){
                i = j;
                total = 0;
            }
            total += nums[j++];
            result = Math.max(result, total);
        }
        return result;

    }
}

// error:为什么不能用区间 dp 做，因为这个题里加和 MAX 不能互相递推得出！！
// 1. 状态定义：f[i][j] 表示 i~j 内子数组和的最大值
// 2. 状态计算：f[i][j] = MAX(f[i][k] + f[k+1][j]) k->(i+1~j)
// 3. 边界：f[~][~] = MIN_VALUE , f[i][i] = nums[i] 

class Solution {
        int n = nums.length;
        int[][] f = new int[n+2][n+2];
        for (int i = 1 ; i <= n ; i++){
            for (int j = 1 ; j <= n ; j ++){
                f[i][j] = i == j ? nums[i-1] : Integer.MIN_VALUE >> 1; 
            }
        }

        for (int len = 2 ; len <= n ; len ++){
            for(int i = 1; i + len -1 <= n ; i++){
                int j = i + len -1 ;
                for (int k = i; k <= j-1 ; k++){
                    f[i][j] = Math.max(f[i][j], f[i][k] + f[k+1][j]);
                }
            }

            for (int i = 1 ;  i + len -1 <= n; i++){
                System.out.printf("%d ", f[i][ i + len -1]);
                System.out.println();
            }
            System.out.println();
        }

        return f[1][n];
}