连续子数组最大和(ACM版本)

总结：
1.本题使用动态规划即可解出，很容易想到遍历到i个元素时，f[i-1]>0,f[i]=f[i-1]+arr[i];f[i-1]<0,f[i]=arr[i],其中f[i]是记录最后一个元素为arr[i]的最大连续子数组之和
2.由于计算f[i]只和上一个状态f[i-1]有关，所以只需记忆上一状态即可，空间复杂度可降为O(1)。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int max,last;//max记录整个数组中最大之和，last记录包含上一个元素的最大连续子数组之和
        last = arr[0];
        max = last;
        for(int i=1;i<n;i++){
            if(last>0){
                last = last+arr[i];//包含当前元素的最大连续子数组之和
                max = Math.max(max,last);
            }else{
                last = arr[i];//包含当前元素的最大连续子数组之和
                max = Math.max(max,last);
            }          
        }
        System.out.println(max);
    }
}

// 只讲一下核心代码，dp问题的关键就是找到状态转移方程也就是递推式 这里的ifelse就是
// 线性dp只考虑选或者不选两种操作是比较简单的思想，那么针对每一个数组中的元素，如果加上之前// 的还更小，那就不要之前的直接用arr[i]，更大的话就加上即arr[i] + dp[i-1]，递推出来
public static long getMax(int n, long[] arr) {
    long[] dp = new long[n];
    dp[0] = arr[0];
    long max = dp[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] + dp[i-1] > arr[i]) dp[i] = arr[i] + dp[i-1];
        else dp[i] = arr[i];
        max = Math.max(max, dp[i]);
    }
    return max;
}