java 牛客网之[动态规划 简单]NC1 子数组最大连续和_给定一个长度为 n 的数组,数组中的数为整数。请你选择一个非空连续子数组,使该子

题目的链接在这里：https://www.nowcoder.com/practice/1718131e719746e9a56fb29c40cc8f95

---

题目大意

给定一个长度为 的数组，数组中的数为整数。 请你选择一个非空连续子数组，使该子数组所有数之和尽可能大。求这个最大值。 输入描述： 第一行为一个正整数 ，代表数组的长度。 1\leq n \leq10^51≤n≤10 5

第二行为 个整数 a_ia
i
​
，用空格隔开，代表数组中的每一个数。 |a_i| \leq 10^9∣a
i
​
∣≤10
9

输出描述：
连续子数组的最大之和。

---

一、示意图

二、解题思路

错误写法 和动态规划
1

暴力

代码如下：

import java.util.*;
public class Main {  
public static void main(String[]args){
                Scanner sc=new Scanner(System.in);
                int n=sc.nextInt();
                int []num=new int[n];
                for(int i=0;i<n;i++){
                        num[i]=sc.nextInt();
                }

                //然后求连续子数组的最大之和
                int sum=0;
                int max=0;
                //先找到第一个大于0 的值
                int temp=0;
                while (temp<n){
                        if(num[temp]<0){
                                temp++;
                        }
                        else{
                                sum+=num[temp];
                                break;
                        }
                }
                max=sum;
                //然后就开始找
                for(int j=temp+1;j<n;j++){
                        //也先进行判断找连续的正数
                        if(num[j]>=0){
                                //说明可以包括在递增序列中
                                sum+=num[j];
                                //然后更新max
                                max=Math.max(max,sum);
                        }
                        else{
                                //一旦出现小于0的 sum就变成0 然后继续赋值
                                sum=0;
                        }

                }
   
        System.out.println(max);

        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

动态规划

代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1;i<nums.length;i++){
                    /*    if(dp[i-1]<0){
                                //说明前面的没用了
                                dp[i]=num[i];

                        }else{
                                //说明前面的是有用的 那就判断哪个大一点
                                dp[i]=dp[i-1]+num[i];
                        }*/
            //直接这么比就行了
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            max=Math.max(max,dp[i]);
        }
        
        return max;
    }
}






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28