一个非空整数数组,选择其中的两个位置,使得两个位置之间的数和最大。
如果最大的和为正数,则输出这个数;如果最大的和为负数或 0 ,则输出 0
数据范围: ,数组中的值满足
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String s = sc.nextLine(); String[] split = s.split(","); int[] a = new int[split.length]; for (int i = 0; i < a.length; i++) { a[i] = Integer.parseInt(split[i]); } int[] dp = new int[a.length]; dp[0] = a[0]; for (int i = 1; i < a.length; i++) { dp[i] = Math.max(dp[i - 1] + a[i], a[i]); } int max = Integer.MIN_VALUE; for (int i = 0; i < a.length; i++) { if (dp[i] > max) max = dp[i]; } System.out.println(max > 0 ? max : 0); } } }
import java.util.Scanner; public class Main { public static int getSum(int[] arr) { //check arr if(arr == null || arr.length <= 0) return 0; int curSum = 0; int maxSum = Integer.MIN_VALUE; for(int i=0; i<arr.length; i++) { if(curSum < 0) { curSum = arr[i]; } else { curSum += arr[i]; } if(curSum > maxSum) { maxSum = curSum; } } return maxSum > 0 ? maxSum : 0; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] arrStr = sc.nextLine().split(","); int[] arr = new int[arrStr.length]; for(int i=0; i<arr.length; i++) arr[i] = Integer.valueOf(arrStr[i]); int result = getSum(arr); System.out.println(result); } }
import java.util.*; public class Main{ public static void main(String [] args){ Scanner sc = new Scanner(System.in); String[] arrstr = sc.nextLine().split(","); int [] arr = new int[arrstr.length]; for(int i = 0; i < arr.length; i ++) arr[i] = Integer.valueOf(arrstr[i]); int top = arr.length - 1; for(int i = 0; i < top; i ++){ if( arr[i] == 0 || arr[i+1] == 0 || ( arr[i] < 0 ) == ( arr[i+1] < 0 ) ){ arr[i] += arr[i + 1]; System.arraycopy(arr, i+2, arr, i+1, top-i-1); top --; i --; } } int[] tmp = new int[top+1]; System.arraycopy(arr, 0, tmp, 0, top+1); System.out.println(func(tmp, 0, 0)); } private static int max = 0; private static int func(int[] arr, int sum, int index){ if( index == arr.length ) return max; max = max >= arr[index] ? max : arr[index]; sum += arr[index]; max = max >= sum ? max : sum; func(arr, sum, index+1); func(arr, 0, index+1); return max; } }