package com.chinahrt.zyn.pango; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Test { /** * 一个整形数组,数组里有正数也有负数。 *数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和,求所有子数组的和的最大值,要求时间复杂度为O(n)。 *例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,那么最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。 * @param i * @return * Administrator * */ public int getMaxSum(Integer[] a){ Integer[] b = getReplaceLeft(a); Integer[] c = getReplaceRight(b); List<Integer> list = megrenArray(c); list = megrenArrayStep2(list); return getMax(list); } //合并list中的数{正,负,正...负,正}(如果负数和前面正数, //后面正数的和比两个正数中的任意一个都大,合并这三个数) public List<Integer> megrenArrayStep2(List<Integer> list){ for(int i=1;i<list.size()-1;){ Integer m = list.get(i); if(m<0){ Integer p = list.get(i-1); Integer n = list.get(i+1); if((m+p+n)>p&&(m+p+n)>n){ list.remove(i-1); list.remove(i-1); list.remove(i-1); list.add(i-1, (p+m+n)); }else{ i+=2; } } } return list; } //把连续的正数求和合并,连续的负数求和合并,返回{正,负,正...负,正}的list public List<Integer> megrenArray(Integer[] a){ List<Integer> list = new ArrayList<Integer>(); for(int i:a){ list.add(i); } for(int i=0;i<list.size()-1;){ int b = (Integer)list.get(i); int c = (Integer)list.get(i+1); if((b>0&&c>0) || (b<0&&c<0)){ list.remove(i); list.remove(i); list.add(i, new Integer(b+c)); }else{ i++; } } System.out.println("step1="+list); return list; } //去除左侧的所有负数 public Integer[] getReplaceLeft(Integer[] i){ Integer[] a; if(i[0]<=0){ a = Arrays.copyOfRange(i, 1,i.length); return getReplaceLeft(a); }else{ a = i; return a; } } //去除右侧的所有负数 public Integer[] getReplaceRight(Integer[] i){ Integer[] a; if(i[i.length-1]<=0){ a = Arrays.copyOfRange(i, 0,i.length-1); return getReplaceRight(a); }else{ a = i; return a; } } //求list中的最大值 private int getMax(List<Integer> list){ int max = 0; for(Integer n:list){ if(n>max){ max = n; } } return max; } /** * @param args * Administrator * */ public static void main(String[] args) { Test t = new Test(); Integer[] a = {1, -2, 3, 10, -4, 7, 2, -5}; System.out.println(t.getMaxSum(a)); } }
相关推荐
扫描法是另一种解决连续子数组最大和问题的方法。这种算法与动态规划解法类似,但其初始化方式略有不同。扫描法中,curSum和maxSum都从0开始,对于数组中的每个元素,将其累加到curSum中。如果curSum变为非正,则...
从头到尾逐个累加示例数组中的每个数字。初始化和为0,第一步加上第一个数字1,...第八步加上最后一个数字-5,由于得到的和为13,小于此前最大和18,因此最终最大的子数组的和为18,对应的子数组是{3,10,-4,7,2}。
这个问题的目标是找到数组中的一个连续子数组,使得这个子数组的所有元素之和最大。 首先,我们需要理解什么是子数组。在数组中,子数组是由数组中任意两个下标i和j(i )确定的一段连续元素的集合,即原数组的第i...
最大和连续子数组问题(Maximum Subarray Problem)是计算机科学中的一个经典问题,特别是在算法设计和分析领域。这个问题源于寻找一个数组(或序列)中具有最大和的连续子数组。这个子数组不一定是连续的,但其元素...
求最大连续子数组.cpp
连续子数组的最大和.md
动态规划之连续子数组的最大和 连续子数组的最大和是动态规划中的一个经典问题,它们要求我们在给定的数组中找到一个连续的子数组,使得该子数组的和最大。这种问题的解决方法有很多,我们今天将介绍两种不同的方法...
在本文中,我们将深入探讨如何解决计算机科学领域中的一道经典问题——寻找连续子数组的最大和。这个问题通常出现在算法竞赛和面试中,例如在LeetCode等在线平台上的题目。我们将采用动态规划的方法来解决这个问题,...
这个问题的目标是给定一个整数数组,找出这个数组中的一个连续子数组,使得其元素之和最大。这个问题的一个著名解决方案是Kadane's Algorithm(卡丹算法),它具有线性时间复杂度,即O(n),其中n是数组的长度。 ...
对于求最大连续子数组和的问题,我们可以维护一个变量`pre_sum`,表示到当前元素为止的最大子数组和,同时还有一个`max_sum`变量,用来记录全局的最大和。遍历数组时,如果`pre_sum`小于0,说明之前的子数组对当前子...
java基础面试题连续子数组的最大和本资源系百度网盘分享地址
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此...
一个整数数组中的元素有正有负,在该数组中找出一个连续子数组,要求该连续子数组中各元素的和最大,这个连续子数组便被称作最大连续子数组。 随机产生1000以上的数据(有正有负),写入文件input.txt 比如数组{2,4,...
连续最大子数组和问题要求找到一个整数数组中的连续子数组,使得该子数组的和最大。例如,对于数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4],最大的子数组和是 6,对应的子数组为 [4, -1, 2, 1]。 提供的代码实现了一个名...
python python_剑指offer第30题连续子数组的最大和
### Python语言描述连续子数组的最大和 #### 题目背景与目标 在日常的数据处理与算法设计中,经常会遇到需要分析数据序列的问题。其中,寻找连续子序列的最大和就是一个非常典型的应用场景。例如,在金融市场分析中...
给一个数组,返回它的最大连续子序列的和使用动态规划F(i):以array[i]为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变res:所有子数组的和的
在编程中,经常遇到寻找数组中连续子数组最大和的问题,这是一个经典的算法问题,通常可以通过不同的方法解决。在Python中,有几种常见的策略,包括蛮力法、利用已计算子数组和以及动态规划。 ### 1. 蛮力法 最直观...