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)); } }
相关推荐
主要介绍了PHP实现求连续子数组最大和问题2种解决方法,涉及php针对数组的遍历、判断、运算等相关操作技巧,需要的朋友可以参考下
从头到尾逐个累加示例数组中的每个数字。初始化和为0,第一步加上第一个数字1,...第八步加上最后一个数字-5,由于得到的和为13,小于此前最大和18,因此最终最大的子数组的和为18,对应的子数组是{3,10,-4,7,2}。
求元素组合成连续子数组之和最大的子数组,要求时间复杂度为O(n)
求最大连续子数组.cpp
连续子数组的最大和.md
40.连续子数组的最大和1
例如,对于数组 [1,-2,4,8,-4,7,-1,-5] 而言,其最大和的子数组为 [4,8,-4,7],最大值为 15。 方法: 蛮力法 重复利用已经计算的子数组和 动态规划 优化的动态规划 1.蛮力法 找出所有的子数组,然后求出...
求数组的子数组之和的最大值,数组中全部为整数,子数组之和即为连续的数组元素相加之和
java基础面试题连续子数组的最大和本资源系百度网盘分享地址
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此...
一个整数数组中的元素有正有负,在该数组中找出一个连续子数组,要求该连续子数组中各元素的和最大,这个连续子数组便被称作最大连续子数组。 随机产生1000以上的数据(有正有负),写入文件input.txt 比如数组{2,4,...
连续子数组的最大和输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。解题思路:动态规划Dp[i]表示 nums 中以 nums[i]结尾的最大子数组和
最大和连续子数组比较熟悉贴个文章http://en.wikipedia.org/wiki/Maximum_subarray_problem。
给一个数组,返回它的最大连续子序列的和使用动态规划F(i):以array[i]为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变res:所有子数组的和的
42. 连续子数组的最大和题目描述{6, -3, -2, 7, -15, 1, 2, 2},连续子数组的最大和为 8(从第 0 个开始,到第 3 个为止)。
主要介绍了python求最大连续子数组的和,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
求一个数组子数组的最大和,这是一道非常经典的公司面试或笔试题目,我分别使用了暴力枚举、分枝界定、动态规划三种算法实现。
求所有子数组的和的最大值,要求时间复杂度为O(n)例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。思路记
剑指 Offer 42. 连续子数组的最大和动态规划const dp: number[] = new Array(nums.length);