输入一个整形数组（可能有正数和负数），求数组中连续子数组（最少有一个元素）的最大和。要求时间复杂度为O(n)。
【重要】第一行为数组的长度N（N>=1）
接下来N行，每行一个数，代表数组的N个元素
最大和的结果
18
思路：这是个需要利用到动态规划的问题
当数组只有一个时，则第一个是最大的子串
当数组有两个时，最大子串就是要么取一个数，要么取两个数
三个同理
import java.util.*; public class Client { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()){ int count = scanner.nextInt(); int[] arr = new int[count]; for (int i = 0; i < count; i++) { arr[i] = scanner.nextInt(); } lenOfSubString(arr); } // int[] arr= {8,1,-2,3}; // lenOfSubString(arr); } private static void lenOfSubString(int[] arr) { int[] dp = new int[arr.length]; dp[0] = arr[0]; for (int i = 1; i < arr.length; i++) { if (dp[i - 1] < 0) { dp[i] = arr[i]; } else { dp[i] = dp[i - 1] + arr[i]; } } int max = dp[0]; for (int i = 1; i < dp.length; i++) { if(dp[i] > max){ max = dp[i]; } } System.out.println(max); } }
原文：https://www.cnblogs.com/dongma/p/13364259.html