题解 | #连续子数组最大和(ACM版本)#

// import java.util.Scanner; import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); long[] arr = new long[n]; for(int i = 0;i < n;i++){ arr[i] = in.nextLong(); } Long[] dp = new Long[n]; dp[0] = arr[0]; for(int i = 1;i < n;i++){ dp[i] = Math.max(dp[i-1]+arr[i],arr[i]);

    }
    Long max = arr[0];
    for(int i = 0;i < n;i++){
        max = max > dp[i] ? max : dp[i];
    }
    System.out.println(max);
}

} // public class Main { // public static void main(String[] args) { // Scanner in = new Scanner(System.in); // int n = in.nextInt(); // long[] arr = new long[n]; // for(int i=0;i<n;i++){ // arr[i] = in.nextLong(); // }

// //定义dp数组 // long dp[] = new long[n]; // dp[0] = arr[0]; // for(int i=1;i<dp.length;i++){ // dp[i] = Math.max(dp[i-1]+arr[i],arr[i]); // }

// long res = Long.MIN_VALUE; // for(int i=0;i<dp.length;i++){ // if(dp[i]>res){ // res = dp[i]; // } // } // System.out.println(res); // } // }