import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); in.nextLine(); int[] nums = new int[n]; //将输入存到数组中 for (int i = 0; i < n; i++) { nums[i] = in.nextInt(); } // dp[i]表示以num[i]结尾的连续子数组的最大值为dp[i] int[] dp = new int[n]; dp[0] = nums[0]; //记录最大值 int max = nums[0]; for (int i = 1; i < nums.length; i++) { //两种情况,nums[i]:从当前num[i]开始计算最大值 //dp[i-1] + nums[i]:num[i]加入当前连续子数组的和 dp[i] = Math.max(nums[i], dp[i-1] + nums[i]); if(dp[i] > max) { //更新最大值 max = dp[i]; } } System.out.println(max); } }
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(); int max = Integer.MIN_VALUE; int sum=0; for(int i=0;i<n;i++){ sum+=in.nextInt(); if(sum>max) max = sum; //必须在后,避免全是负数的情况 if(sum<0) sum=0; } System.out.println(max); } }
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int len = in.nextInt(); int preNum = 0; int maxAns = in.nextInt(); while (in.hasNextInt()) { int a = in.nextInt(); preNum = Math.max(preNum + a, a); maxAns = Math.max(maxAns, preNum); } System.out.println(maxAns); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = scan.nextInt(); } int sum = arr[0]; int max = arr[0]; for (int i = 1; i < n; i++) { sum = getMax(sum+arr[i],arr[i]); if(sum > max) { max = sum; } } System.out.println(max); } public static int getMax(int a,int b) { return a > b ? a : b; } }
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 sum = arr[0]; int max = arr[0]; //动态规划的方法 for(int i = 0;i < arr.length;i++){ sum = Math.max(sum + arr[i],arr[i]); max = Math.max(max,sum); } System.out.println(max); } }
import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arr = br.readLine().split(" "); int n = Integer.parseInt(arr[0]); int max = Integer.MIN_VALUE, dp = 0; arr = br.readLine().split(" "); for (int i = 0; i < n; i++) { dp += Integer.parseInt(arr[i]); if(max < dp){ max = dp; } if(dp < 0){ dp = 0; } } System.out.println(max); } }java
import java.util.*; public class Main { public static void main (String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int arr[] = new int[n]; for (int i = 0; i < n; i++) { arr[i] = in.nextInt(); } int max = Integer.MIN_VALUE; int sum = 0; for (int j = 0; j < n; j++) { sum += arr[j]; if (sum > max) { max = sum; } if (sum < 0) { sum = 0; } } System.out.print(max); } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n]; for(int i = 0; i < n; i++){ nums[i] = sc.nextInt(); } int sum = nums[0]; for(int i = 1; i < n; i++){ nums[i] += Math.max(nums[i - 1], 0); sum = Math.max(nums[i], sum); } System.out.println(sum); } }滑动窗口的思想
import java.util.Scanner; public class Main { public static void main(String args[]){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int []a = new int[n]; for (int i = 0; i <n ; i++) { a[i] = sc.nextInt(); } int max = a[0],sum = a[0]; for (int i = 1; i < a.length; i++) { if(sum+a[i]>a[i]){ sum = sum+a[i]; }else { sum = a[i]; } if(sum>max) max = sum; } System.out.println(max); } }
不需要建立数组啊~ 不断累加,只要小于0,清零,重新开始 只需要记录过程中的最大值 import java.util.Scanner; public class Main{ public static void main(String [] args){ Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); int max=Integer.MIN_VALUE,temp=0; for(int i=0;i<n;i++){ temp+=sc.nextInt(); if(temp>max) max=temp; if(temp<=0) temp=0; } System.out.println(max); } } }
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int array[]=new int[n];
for(int i=0;i<n&&sc.hasNext();i++) {
array[i]=sc.nextInt();
}
TreeSet ts=new TreeSet();
int sum=0;
for(int i=0;i<n;i++){
if(sum>=0){
sum += array[i];
}else{
sum=array[i];
}
ts.add(sum);
}
Iterator it=ts.iterator();
String[] strs=new String[ts.size()];
for(int i=0;i<ts.size()&&it.hasNext();i++) {
strs[i]=it.next().toString();
}
System.out.println(strs[ts.size()-1]);
}
}
利用TreeSet集合的有序性
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int []arr = new int[n]; for (int i = 0;i < n;i ++) { arr[i] = scanner.nextInt(); } long max = max(arr); System.out.println(max); } public static long max(int []arr) { long max = arr[0]; long sum = arr[0]; for (int i = 0;i < arr.length;i ++) { if (sum + arr[i] < 0) { sum = 0; }else { sum += arr[i]; max = Math.max(max, sum); } max = Math.max(max, arr[i]); } return max; } }
import java.util.Scanner;
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();
}
System.out.println(FindGreatestSumOfSubArray(arr));
}
public static int FindGreatestSumOfSubArray(int[] array) {
if(array.length==0)
return 0;
int sum = array[0];//保存每组的和
int maxSum = array[0];//连续子数组最大和
//动态规划
for(int i = 1;i<array.length;i++){
sum = Math.max(sum+array[i],array[i]);
maxSum = Math.max(sum,maxSum);
}
return maxSum;
}
}