最大子数组和

原题链接

使用的方法

• Math.max(): 返回两个数中的较大值。

解题思路

• 使用动态规划方法，定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最大子数组和。
• 初始化 dp[0] 为 nums[0]，并设置一个变量 res 来记录全局最大子数组和。
• 遍历数组 nums，对于每个元素 nums[i]，计算 dp[i] 的值，它等于 dp[i-1] + nums[i] 和 nums[i] 中的较大值。
• 更新全局最大子数组和 res，如果 dp[i] 大于 res，则更新 res。
• 最后返回 res，即为最大子数组和。

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i=1;i<nums.length;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            if(res < dp[i]) res = dp[i];
        }
        return res;
    }
}