LeetCode53. 最大子数组和

思路

1.定义dp数组

dp[i]表示以数组下标为i结尾的子数组的最大值。

2.递推公式

dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);

3.dp数组的初始化

dp[0] = nums[0];

4.遍历顺序

根据递推公式可以知道是正序遍历

5.打印dp数组

最接找到dp数组中最大的数就是最后的结果

代码

class Solution {    public int maxSubArray(int[] nums) { 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]); } int max = nums[0]; for(int i =0;i<nums.length;i++){     max = Math.max(max,dp[i]); } return max;    }}