leetcode53 -最大子数组和 Java

class Solution {
    public int maxSubArray(int[] nums) {
        
        int n = nums.length;
        if(n == 0) return 0;
        int[] dp = new int[n];

        // 第一个元素前面没有子数组,前面没有的话直接进行赋值即可
        dp[0] = nums[0];
        // 状态转移方程
        for(int i = 1; i < n; i++){
            // 因为i从0开始的话，肯定会出事的
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }
        // 上面的for循环就能找到相应的最大子数组的和，这一点还是很关键的
        // 然后通过遍历数组dp以此来得到nums的最大子数组
        int res = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

使用了一个数组用来每次接收更新以后的前面n个数据的最大和，最后在这个数组中查找即可