`
zyn010101
  • 浏览: 325090 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

求连续子数组的最大和

阅读更多
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));
		
	}

}

 

0
4
分享到:
评论

相关推荐

    PHP实现求连续子数组最大和问题2种解决方法

    扫描法是另一种解决连续子数组最大和问题的方法。这种算法与动态规划解法类似,但其初始化方式略有不同。扫描法中,curSum和maxSum都从0开始,对于数组中的每个元素,将其累加到curSum中。如果curSum变为非正,则...

    连续子数组的最大和

    从头到尾逐个累加示例数组中的每个数字。初始化和为0,第一步加上第一个数字1,...第八步加上最后一个数字-5,由于得到的和为13,小于此前最大和18,因此最终最大的子数组的和为18,对应的子数组是{3,10,-4,7,2}。

    数组中最大和的子数组

    这个问题的目标是找到数组中的一个连续子数组,使得这个子数组的所有元素之和最大。 首先,我们需要理解什么是子数组。在数组中,子数组是由数组中任意两个下标i和j(i )确定的一段连续元素的集合,即原数组的第i...

    最大和连续子数组1

    最大和连续子数组问题(Maximum Subarray Problem)是计算机科学中的一个经典问题,特别是在算法设计和分析领域。这个问题源于寻找一个数组(或序列)中具有最大和的连续子数组。这个子数组不一定是连续的,但其元素...

    求最大连续子数组.cpp

    求最大连续子数组.cpp

    连续子数组的最大和.md

    连续子数组的最大和.md

    40.连续子数组的最大和1

    动态规划之连续子数组的最大和 连续子数组的最大和是动态规划中的一个经典问题,它们要求我们在给定的数组中找到一个连续的子数组,使得该子数组的和最大。这种问题的解决方法有很多,我们今天将介绍两种不同的方法...

    连续子数组的和1

    在本文中,我们将深入探讨如何解决计算机科学领域中的一道经典问题——寻找连续子数组的最大和。这个问题通常出现在算法竞赛和面试中,例如在LeetCode等在线平台上的题目。我们将采用动态规划的方法来解决这个问题,...

    求子数组最大和

    这个问题的目标是给定一个整数数组,找出这个数组中的一个连续子数组,使得其元素之和最大。这个问题的一个著名解决方案是Kadane's Algorithm(卡丹算法),它具有线性时间复杂度,即O(n),其中n是数组的长度。 ...

    python求最大连续子数组的和

    对于求最大连续子数组和的问题,我们可以维护一个变量`pre_sum`,表示到当前元素为止的最大子数组和,同时还有一个`max_sum`变量,用来记录全局的最大和。遍历数组时,如果`pre_sum`小于0,说明之前的子数组对当前子...

    java基础面试题连续子数组的最大和

    java基础面试题连续子数组的最大和本资源系百度网盘分享地址

    C语言程序:求子数组的最大和

    数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此...

    算法-分治法求解最大子数组问题

    一个整数数组中的元素有正有负,在该数组中找出一个连续子数组,要求该连续子数组中各元素的和最大,这个连续子数组便被称作最大连续子数组。 随机产生1000以上的数据(有正有负),写入文件input.txt 比如数组{2,4,...

    连续最大子数组和1

    连续最大子数组和问题要求找到一个整数数组中的连续子数组,使得该子数组的和最大。例如,对于数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4],最大的子数组和是 6,对应的子数组为 [4, -1, 2, 1]。 提供的代码实现了一个名...

    python-剑指offer第30题连续子数组的最大和

    python python_剑指offer第30题连续子数组的最大和

    Python语言描述连续子数组的最大和

    ### Python语言描述连续子数组的最大和 #### 题目背景与目标 在日常的数据处理与算法设计中,经常会遇到需要分析数据序列的问题。其中,寻找连续子序列的最大和就是一个非常典型的应用场景。例如,在金融市场分析中...

    dahuzi998#2018-Java-Interview#算法-动态规划-连续子数组最大和1

    给一个数组,返回它的最大连续子序列的和使用动态规划F(i):以array[i]为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变res:所有子数组的和的

    python如何求数组连续最大和的示例代码

    在编程中,经常遇到寻找数组中连续子数组最大和的问题,这是一个经典的算法问题,通常可以通过不同的方法解决。在Python中,有几种常见的策略,包括蛮力法、利用已计算子数组和以及动态规划。 ### 1. 蛮力法 最直观...

Global site tag (gtag.js) - Google Analytics