首页 > 试题广场 >

写程序实现功能。 输入是具有 n 个浮点数的数组,输出是输入

[问答题]

写程序实现功能。

输入是具有 n 个浮点数的数组,输出是输入数组的任何连续子数组中的最大和。例如,如果输入数组中包含下面 10 个元素: {31,-41,59,26,-53,58,97,-93,-23,84} ,那么该程序的输出为 {59,26,-53,58,97} 的总和,即 187

剑指Offer-连续子数组的最大和

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;
    }
}
发表于 2018-04-14 15:31:50 回复(0)
更多回答
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;
      }
     }
}
}
      


发表于 2018-04-15 19:36:30 回复(0)
//最大连续子求和啊,  算法里面最基本的问题
float maxSum(float a[],int n)  //浮点数组a,里面有n个元素
{
    int i=0;
float sum=0,maxSum=0;
for(i=0;i<n;i++)
{
if(sum>maxSum)
maxSum=sum;
if(sum>=0)
{
sum+=a[i];
}
else
{
sum=a[i];
}
}
return maxSum;
}
发表于 2017-02-18 15:05:10 回复(4)