写程序实现功能。
输入是具有 n 个浮点数的数组,输出是输入数组的任何连续子数组中的最大和。例如,如果输入数组中包含下面 10 个元素: {31,-41,59,26,-53,58,97,-93,-23,84} ,那么该程序的输出为 {59,26,-53,58,97} 的总和,即 187 。import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
float[] arr = new float[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextFloat();
}
System.out.println(FindGreatestSumOfSubArray(arr));
}
public static float FindGreatestSumOfSubArray(float[] array) {
if (array.length == 0)
return 0;
float sum = array[0];//保存每组的和
float 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;
}
}
float maxSum(float a[], int n) { int i = 0; float sum = a[0], maxSum = a[0]; for (i = 1; i<n; i++) { if (sum>maxSum) { maxSum = sum; } if (sum >= 0) { sum += a[i]; if(i == n - 1) { if (sum > maxSum) return sum; else return maxSum; } else { sum = a[i]; if (i == n - 1) { if (a[i] > maxSum) return a[i]; else if (sum > maxSum) return sum; else return maxSum; } } } }