连续子数组最大和

[编程题]连续子数组最大和

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

输入一个整形数组（可能有正数和负数），求数组中连续子数组（最少有一个元素）的最大和。要求时间复杂度为O(n)。

输入描述:

【重要】第一行为数组的长度N（N>=1）

接下来N行，每行一个数，代表数组的N个元素

输出描述:

最大和的结果

示例1

输入

输出

说明

最大子数组为 3, 10, -4, 7, 2

算法知识视频讲解

Java

凌晨两点敲代码

import java.util.*;
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 res=power(a);
        System.out.print(res);
    }
    //动态规划，dp存的是当前长度数组连续子数组的最大和
    static int power(int[] a){
        int [] dp = new int[a.length];
        dp[0]=a[0];
        for(int i=1;i<a.length;i++){
            dp[i] = Math.max(a[i],dp[i-1]+a[i]);
        }
        Arrays.sort(dp);
        return dp[a.length-1];
    }
}

发表于 2021-08-30 22:45:09 回复(0)

Java

何止hz

动态规划入门题目

import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-12 20:33
 * @Description: 连续子数组最大和
 * @version: 1.0
 */
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 cur = arr[0];
        int ans = cur;
        for (int i = 1; i < N; i++){
            cur = Math.max(cur + arr[i], arr[i]);
            ans = Math.max(ans, cur);
        }
        System.out.println(ans);
    }
}

发表于 2020-05-12 20:45:49 回复(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++){
            sc.nextLine();
            arr[i] = sc.nextInt();
        }
        System.out.println(maxSubArray(arr));
    }
    public static int maxSubArray(int[] nums) {
        int n = nums.length;
        int currSum = nums[0], maxSum = nums[0];
        for(int i = 1; i < n; ++i) {
        currSum = Math.max(nums[i], currSum + nums[i]);
        maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
}
}

发表于 2020-04-14 18:57:30 回复(0)

Java

asuren

思路：求出每个位置的累加和，标记最大累加和、最小累加和的位置，分别记为i和j

如果i>j，且sums[j]为负数，说明最大和的连续子数组在i和j之间，返回sums[i]-sums[j]

如果i<=j，说明最大和的连续子数组在0和j之间，返回sums[i]

arr[]: 1 -2 3 10 -4 7 2 -5

sums[]: 1 -1 2 12 8 15 17 12

min max

结果 = 17 - （-1） = 18

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();
        }
        int[] sums = new int[N];
        sums[0]=arr[0];
        
        int max = 0;
        int min = 0;
        
        for(int i=1;i<N;i++){
            sums[i] = sums[i-1]+arr[i];
            max = sums[max]>sums[i]?max:i;
            min = sums[min]<sums[i]?min:i;
        }
        if(max>min){
            int ret = sums[max]>sums[max]-sums[min]?sums[max]:sums[max]-sums[min];
            System.out.println(ret);
        }else{
            System.out.println(sums[max]);
        }
    }
}

发表于 2019-07-06 19:57:26 回复(0)