【CT】LeetCode手撕—53. 最大子数组和

题目

• 原题连接：53. 最大子数组和

1-思路

动规五部曲

• 1. 定义 dp 数组
  • dp[i] 含义为：下标为 i 的数组的最大子数组和
• 2. 递推公式
  • 因为所求的是最大子数组的和，即当前 nums 可加可不加，则需要在 dp[i-1]+nums[i] 和 nums[i] 两者中取一个较大的
  • dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
• 3. 初始化
  • dp[0] = nums[0]
• 4. 遍历顺序
  • 从 i = 0 遍历到 n-1

2- 实现

⭐53. 最大子数组和——题解思路

class Solution {
    public int maxSubArray(int[] nums) {
        // 1. 定义 dp数组
        // 
        int[] dp = new int[nums.length];

        // 2.递推公式
        // dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);

        // 3.初始化
        dp[0] = nums[0];

        // 4. 遍历顺序
        for(int i = 1 ; i < nums.length;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
        }

        int res = nums[0];
        for(int i:dp){
            res = Math.max(res,i);
        }
        return res;
    }
}

3- ACM 实现

public class maxSubNums {


    // 求 最大子数组和
    public static int maxSub(int[] nums){
        // 1.dp数组
        int[] dp = new int[nums.length];

        // 2.递推公式
        // dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);

        // 3.初始化
        dp[0] = nums[0];

        // 4.遍历顺序
        int res = nums[0];
        for(int i = 1 ; i < nums.length;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            res = Math.max(res,dp[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入数组的长度");
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0 ; i < n;i++){
            nums[i] = sc.nextInt();
        }
        System.out.println("最大子数组和为"+maxSub(nums));
    }
}