10、连续子数组最大和

怼烎@ 2022-05-27 10:19 176阅读 0赞

给定一个数组，求连续的几个子元素构成最大和的子集合：

public class findMaxSum {
    
        public int FindGreatestSumOfSubArray(int[] array) {
    
            if(array == null || (array.length == 1 && array[0] <= 0))
                return 0;
    
            int cur = array[0];
            int sum = array[0];
            for(int i = 1;i < array.length;i++){
                if(cur < 0)
                    cur = 0;
                cur = cur + array[i];
                if(sum <= cur)
                    sum = cur;
            }
            return sum;
        }
    
        //用动态规划
        public int FindGreatestSumOfSubArray2(int[] arr,int n){
            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;
            }
            return max;
        }
    
        public int getMax(int a,int b){
            return a > b ? a: b;
        }
    
    
        public static void main(String args[]){
            findMaxSum ts = new findMaxSum();
            int[] a = {
       13,-30,5,4} ; //13
            System.out.println(ts.FindGreatestSumOfSubArray(a));
            System.out.println(ts.FindGreatestSumOfSubArray2(a,a.length));
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关最大连续和（子串）

了4种方法实现： include<bits/stdc++.h> using namespace std; typedef long long l...

青旅半醒/ 2024年04月17日 05:22/ 0 赞/ 42 阅读

相关连续子数组最大和--牛客NC19

描述输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。数据范围: ![e2833950

约定不等于承诺〃/ 2024年04月01日 14:12/ 0 赞/ 38 阅读

相关 golang 连续子数组的和最大值

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。输入: [-2,1,-3,4,-1,2,1,-5,4],

朱雀/ 2023年02月10日 05:24/ 0 赞/ 109 阅读

相关【LeetCode】连续子数组、子矩阵最大和问题

【LeetCode】连续子数组、子矩阵最大和问题文章目录【LeetCode】连续子数组、子矩阵最大和问题连续子数组的最大和★

曾经终败给现在/ 2022年11月13日 13:29/ 0 赞/ 153 阅读

相关和最大的连续子数组

和最大的连续子数组，LeetCode标签：剑指 Offer 42. 连续子数组的最大和 int maxSubArray(vector<int>& nums) {

﹏ヽ暗。殇╰゛Y/ 2022年09月15日 15:51/ 0 赞/ 141 阅读

相关连续子数组最大和问题

1. 问题描述输入一个整形数组，求数组中连续的子数组使其和最大。比如，数组x ![132021534183635.png][] 应该返回 x\[2..6\]的和1

冷不防/ 2022年07月18日 01:12/ 0 赞/ 170 阅读

相关 10、连续子数组最大和

给定一个数组，求连续的几个子元素构成最大和的子集合： public class findMaxSum { public int FindGr

怼烎@/ 2022年05月27日 10:19/ 0 赞/ 177 阅读

相关最大连续子数组问题延伸探讨

假设存在一个这样的数组array，需要求出它的连续子数组，使得该子数组的和最大。例如这样的一个数组：1, -2, 3, 10, -4, 7, 2, -5 最大子

分手后的思念是犯贱/ 2022年05月27日 01:50/ 0 赞/ 143 阅读

相关数据结构-最大连续子数组

【题目来自灰灰考研】在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的

矫情吗；*/ 2022年05月19日 09:40/ 0 赞/ 181 阅读

相关 [剑指offer]连续子数组最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。

古城微笑少年丶/ 2021年11月22日 11:46/ 0 赞/ 249 阅读