【Java版oj】day05连续子序列

青旅半醒 2024-03-31 17:27 84阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

--------------------

> ## 一、原题再现 ##
> 
> [连续最大和\_牛客题霸\_牛客网][Link 1]
> 
> ### 描述 ###
> 
> 一个数组有 N 个元素，求连续子数组的最大和。 例如：\[-1,2,1\]，和最大的连续子数组为\[2,1\]，其和为 3
> 
> #### 输入描述： ####
> 
> 输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。
> 
> #### 输出描述： ####
> 
> 所有连续子数组中和最大的值。
> 
> 示例1
> 
> 输入：
> 
> 3
> 
> \-1 2 1
> 
> 输出：
> 
> 3

> ## 二、问题分析 ##
> 
> 本题是典型的动态规划问题，简称dp问题。
> 
> 状态方程式： max( dp\[ i \] ) = getMax( max( dp\[ i -1 \] ) + arr\[ i \] ,arr\[ i \] )  
> dp\[i\] 就是以数组下标为 i 的数做为结尾的最大子序列和，注意是以 i 为结尾，比如说现在有一个数组\{6,-3,-2,7,-15,1,2,2\}，dp\[2\]就是以-2为结尾的，那么显然dp\[3\]的最大值就是1咯（6，-3，-2），dp\[3\]要以7结尾那么以7结尾的子序列最大和就是8（6，-3，-2，7）。现在我们开始细细品一下上面这个递推式，求dp\[i\]的时候是不是有两种可能，要么就是像上面的dp\[3\]一样，dp\[2\]求出来是1了，再加上自己array\[3\]是最大的，那么还有一种可能就是说如果dp\[2\]我求出来是-100，那如果我也是dp\[2\]+array\[3\]的话是-93， 这时候dp\[2\]反而是累赘，最大就是自己（因为前面定义了必须以i为结尾，也就说必须以7结尾）。
> 
> 方法一是直接在输入的时候进行处理；方法二是将输入的数放入数组中进行处理。

> ## 三、完整代码 ##
> 
>     import java.util.*;
>     import java.lang.*;
>     public class Main {
>         public static void main(String[] args) {
>             List<Character>list = new ArrayList<>();
>             Scanner in = new Scanner(System.in);
>             int n = in.nextInt();
>             int sum = 0;
>             int ans = Integer.MIN_VALUE;//考虑数组全是负数情况
>             for (int i = 0; i < n; i++) {
>                 int num = in.nextInt();
>                 sum += num;
>                 ans = Math.max(sum, ans);
>                 sum = sum < 0 ? 0 : sum;
>             }
>             System.out.println(ans);
>         }
>     }
> 
> ![77f2bd2f277241b695f7674542522cb7.png][]
> 
>     import java.util.Scanner;
>     public class Main {
>         public static int GetMax(int a, int b) { //得到两个数的最大值
>             return (a) > (b) ? (a) : (b);
>         } 
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             int size = sc.nextInt();
>             int[] array = new int[size];
>             for (int i = 0; i < size; i++) {
>                 array[i] = sc.nextInt();
>             } 
>             int sum = array[0];
>             int max = array[0];
>             for (int i = 1; i < size; i++) {
>                 sum = GetMax(sum + array[i], array[i]); //状态方程
>                 if (sum >= max)
>                     max = sum;
>             } 
>             System.out.println(max);
>         }
>     }
> 
> ![4b296e8c79104365af5d88ab12217558.png][]

--------------------

![762cdbddb31c4e5e95b872a229aa692e.png][]

[Link 1]: https://www.nowcoder.com/practice/5a304c109a544aef9b583dce23f5f5db?tpId=85&&tqId=29858&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
[77f2bd2f277241b695f7674542522cb7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/63be6c91c12c4fad8498948586f2ec3d.png
[4b296e8c79104365af5d88ab12217558.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/31528e8a3eaa4973a69c60476f51deb2.png
[762cdbddb31c4e5e95b872a229aa692e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/841151ff4ca24b1a82890e75f350966d.png