首页 > 试题广场 >

连续最大和

[编程题]连续最大和

热度指数：59463 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个数组有 N 个元素，求连续子数组的最大和。例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3

输入描述:

输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。

输出描述:

所有连续子数组中和最大的值。

示例1

输入

3
-1 2 1

输出

算法知识视频讲解

Java

xiaoL9

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);
    }
}

发表于 2023-08-10 11:13:09 回复(0)

Java

许七

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);
    }
}

发表于 2023-05-08 21:03:58 回复(0)

Java

牛客678979344号

真的是阅读理解题呀

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);
    }
}

发表于 2023-01-07 10:50:46 回复(0)

Java

qinli

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 res = nums[0];
for(int i=1;i<n;i++){
nums[i] += Math.max(nums[i-1],0);
res = Math.max(res,nums[i]);
}
System.out.println(res);
}
}

发表于 2022-09-08 13:00:44 回复(0)

Java

抓住努力的尾巴

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;
    }
}

编辑于 2022-04-01 19:37:38 回复(0)

Java

来学习的小张

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);
    }
}

发表于 2022-03-27 19:02:11 回复(0)

Java

wyllyh123456

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

发表于 2022-03-26 12:12:08 回复(0)

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);
    } 
}

发表于 2021-12-28 09:35:28 回复(0)

Java

七宝酱~

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);
    }
}

滑动窗口的思想

发表于 2021-12-23 21:33:29 回复(0)

Java

4.435km/s

动态规划

状态转移方程 sum = max(sum[i-1]+a[i],a[i])

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);
    }
}

发表于 2020-03-13 20:23:26 回复(0)

Java

OKO

public class Main {

public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n = scan.nextInt();
int sum=0;
int max=Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
sum+=scan.nextInt();
if (sum>max) {
max=sum;
}
if (sum<0) {
sum=0;
}
}
System.out.println(max);
}
}

编辑于 2018-09-29 20:21:45 回复(0)

Java

对方没有名称

不需要建立数组啊～
不断累加，只要小于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);
        }
    }
}

发表于 2018-07-07 21:24:18 回复(4)

Java

ん霍霍🍀

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集合的有序性

发表于 2018-06-23 21:38:05 回复(0)

Java

黄小斜

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;
    }
}

发表于 2018-05-27 21:21:17 回复(0)

Java

傲娇小王子

http://www.cnblogs.com/52circle/p/9025595.html
import java.util.Arrays;

import java.util.Scanner;

public class Main {
   public static int getmax(int n,int [] arr) {
       int []max=new int[n];
       max[0]=arr[0];
       for (int i = 0; i < arr.length-1; i++) {
           if (max[i]+arr[i+1]>arr[i+1]) {
               max[i+1]=max[i]+arr[i+1];
           }else {
               max[i+1]=arr[i+1];
           }
       }
       Arrays.sort(max);
       return max[n-1];
   }

   public static void main(String[] args) {
       Scanner scanner=new Scanner(System.in);
       int n=scanner.nextInt();
       int a[]=new int [n];
       for (int i = 0; i < a.length; i++) {
           a[i]=scanner.nextInt();
       }
       System.out.println(getmax(n ,a ));
   }
}

发表于 2018-05-11 17:11:58 回复(0)

Java

kkfarm

package NewWorkNet;

import java.util.Arrays;
import java.util.Scanner;

public class testDemo {

   public static void main(String[] args) {
       int n;
       Scanner sc = new Scanner(System.in);
       n = sc.nextInt();
       int[]sequence = new int[n];
       for(int i=0;i<n;i++){
           sequence[i] = sc.nextInt();
       }
       int tempSum = 0;
       int maxSum = 0;
       int first=0,end=0,tempfirst=0;
       int flag = 0;
       for(int i=0;i<sequence.length;i++){
           if(sequence[i]>=0){
               flag=1;
           }
           tempSum += sequence[i];
           if(tempSum<=0){
               tempSum = 0;
               tempfirst = i + 1;
           }
           else{
               if(tempSum>maxSum){
                   maxSum = tempSum;
                   end = i;
                   first = tempfirst;

               }
           }
       }
//       for(int i=first;i<=end;i++){
//           System.out.print(sequence[i]+" ");
//       }
//       System.out.println();
       if(flag==0){
           Arrays.sort(sequence);
           System.out.println(sequence[sequence.length-1]);
       }
       else{
           System.out.println("maxSum:"+maxSum);
       }

   }

}
包括连续最大和的起始和终点位置

发表于 2018-05-10 21:32:58 回复(0)

Java

武培轩

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

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;
    }
}

发表于 2018-04-14 15:25:46 回复(0)

Java

李狗什么

//动态规划

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int temp = 0;
int max = Integer.MIN_VALUE;
int num = sc.nextInt();
for(int i = 0;i<num;i++){
int val = sc.nextInt();
temp = Math.max(temp+val,val);
if(temp>max){
max = temp;
}
}
System.out.println(max);
}
}

发表于 2018-03-24 16:02:15 回复(0)

Java

南山寻鹤

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

    public static void main(String[] args) throws IOException {

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       String str1 = br.readLine();
       String str2 = br.readLine();
       int n = Integer.parseInt(str1);
       String[] arrStr2 = str2.trim().split(" ");
       int[] arr = new int[n];
       int thisSum = 0;
       int maxSum = 0;
        boolean allFu = true;
       for (int i=0;i<arrStr2.length;i++ ) {
           arr[i] = Integer.parseInt(arrStr2[i]);
            if(arr[i]>=0) allFu = false;
        }

        if(allFu){
            maxSum = arr[0];
        } else{
            for (int i=0;i<arrStr2.length;i++ ) {
           arr[i] = Integer.parseInt(arrStr2[i]);
           thisSum += arr[i];
           if(thisSum > maxSum) {
               maxSum = thisSum;
           } else if(thisSum < 0) {
               thisSum = 0;
                }
            }
        }
       System.out.println(maxSum);
            }
}

全负的情况要分开讨论……

发表于 2018-03-20 22:08:21 回复(0)