经典算法动态规划（dp问题归纳)

1，线性dp求连续子区间问题

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

栗子：

输入：1 -2 3 10 -4 7 2 -5

输出 ：18

import java.util.Scanner;
public class Main{
    public static void main(String[]args)
    {
        Scanner input=new Scanner(System.in);
        int n= input.nextInt();
        int []ant=new int[n];
        int []num=new int[n];
        int sum=0;
        for(int i=0;i<n;i++)
        {
            ant[i]= input.nextInt();
        }
        num[0]=ant[0];
        for(int i=1;i<n;i++)//不需要求前缀和
        {
            num[i]=num[i-1]+ant[i];

        }
        for(int i=0;i<n;i++)
        {
            System.out.print(num[i]+" ");
        }
        int pre = 0;int maxAns = ant[0];
        for (int x : ant) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        System.out.println(maxAns);
    }

}