最大字段和

- 日理万妓 2022-07-29 11:50 188阅读 0赞

N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。
    例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
    Input
    第1行：整数序列的长度N（2 <= N <= 50000)
    第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）
    Output
    输出最大子段和。
    Input示例
    6
    -2 11
    -4 13
    -5 -2 Output示例
    20

1.  b\[j\]代表以a\[j\]为结尾的所有字段的最大字段和，也就是说**b\[j\]一定包含a\[j\]**，且这个子段中的所有元素都是输入序列中连续的。
2.  b\[j\]的值由b\[j-1\]结合a\[j\]的值推得，具有最优子结构性质。

> 记b\[j\]=max(a\[i\]+a\[i+1\]+..+a\[j\]),其中1<=i<=j,并且1<=j<=n。则所求的最大子段和为max b\[j\]，1<=j<=n。  
> 由b\[j\]的定义可易知，当b\[j-1\]>0时b\[j\]=b\[j-1\]+a\[j\]，否则b\[j\]=a\[j\]。故b\[j\]的动态规划递归式为:  
> b\[j\]=max(b\[j-1\]+a\[j\],a\[j\])，1<=j<=n。

根据状态转换方程，如果仅是用来求最大子段和的话，没必要在开一个辅助数组b，一遍for循环，使用一个滚动变量进行迭代就可以了。

import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                int n = in.nextInt();
                int[] a = new int[n+10];
                long res = 0,maxSum = 0;
                for(int i=0;i<n;i++){
                    a[i] = in.nextInt();
                    //根据前一子段值的正负进行讨论，若其小于0，则直接赋值为a[i],因为此时无论a[i]正负，加上前一子段的和都比a[i]小，不取！若其大于0，根据状态的意义，这时无论a[i]正负，都必须加上，因为b[j]代表以a[j]结尾的子段。
                    if(maxSum>0) maxSum += a[i];
                    else maxSum = a[i];
                    if(res<maxSum) res = maxSum;
                }
                System.out.println(res);
            }
        }
    
    }