您现在的位置是:首页 > 正文

JAVA 实现循环数组的最大在、连续子数组的和

2024-03-01 11:58:54阅读 27

剑指Offer上有类似的题目:

-------------->求数组连续子数组的最大和为多少?

-------------->求循环数组连续子数组的最大和为多少?

数组好说 判断之前节点的sum < 0;没必要拿本数,去还债,直接设置sum=a[i];依次循环 

【重点max 最开始要被初始化为 Integer.MIN_VALUE】

循环数组:关键在于,找到的sum 有两种可能的情况:

1.sum 是由首尾之间的子数组构成的;

2.sum 由尾部分+首部分构成,抛弃了中间一部分数组。为什么中间被抛弃:因为他们的和是负数,且是和最小的部分。

但是循环数组会有一个问题,如果全部为负,1得到的一定是最大的那个负数,2.会得到0,那么最后会输出0.所以要避免。

情况1,和数组方法一样;

情况2的重点在于:找到中间部分->对数组求导找到maxsum,就是反数的min部分。然后用数组总和SUM-(-maxsum);

连续数组最大和:


  
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int flag = 0; int cursum = 0; int result = 0x80000000;
        //32位int范围(0x80000000,0xFFFFFFF)~(0,0x7FFFFFFF)
        for(int i = 0;i<array.length;i++){
            if(cursum <=0){
                //cursum = 0;//错误
                cursum = array[i];
            }
            else{
                cursum += array[i];
            }
            if(cursum > result)
                result = cursum;
        }
        return result;
    }
}

循环数组的连续子数组的最大和:


public class Main {
	private static  int max = Integer.MIN_VALUE;
	public static void main(String[] args) {
		int[] a={-3,-1,0,-6,-2};int n=a.length;
		int[]b=new int[n];int sum=0;
		//第一种情况,正常,最大max数组的取值在首尾之间
		boolean allfushu=true;
		for(int i=0;i<n;i++){
			if(a[i]>=0)
				allfushu=false;
		}
		int sum1=find(a,n);
		 //第二种情况,部分头+部分尾;中间部分没选择,因为他们的sum最小且为负
		//所以才启发了思路去找没被选中的中间部分:将数组取反 重新找max
		for(int i=0;i<n;i++){
			b[i]=-a[i];
			sum+=a[i];//sum是数组总和
		}
		if(!allfushu){
			int temp = find(b,n);
			int sum2 = sum+temp;
			//这里少考虑一种情况:数值全为负的时候,循环数组的最大子数组的和 
			//第一种算出来是-1,而第二种算出来为0,如果不允许是空串的话应该最后结果为-1的
			//所以这里最好加一个判断,如果全为负直接用第一种就行,不要第二种判断了,否则会导致出错。			
			max = Math.max(sum1, sum2);
			System.out.print(max);
		}
		else {
			System.out.print(sum1);
		}
		
	}
	public static int find(int[]a,int n){
		if(a==null)
			return 0;
		int sum =a[0];	int max1=max;
		for(int i=1;i<n;i++){		
			if(sum<=0)
				sum=a[i];
			else 
				sum+=a[i];
			max1 = max1<sum?sum:max1;
		}
		return max1;
	}


}

网站文章

  • Mybatis动态SQL(详细介绍)

    Mybatis动态SQL(详细介绍)

    Mybatis的动态SQL介绍及应用——详细介绍

    2024-03-01 11:58:45
  • Could not initialize class sun.awt.X11GraphicsEnvironment

    Could not initialize class sun.awt.X11GraphicsEnvironment

    在后面加上-Djava.awt.headless=true,然后保存,把本地的文件放进bin目录下,替换掉以前的catalina.sh文件,然后重启,就ok了。在服务器上找到tomcat的安装目录,再到bin目录下找到catalina.sh文件。

    2024-03-01 11:58:37
  • eclipse 构建 jpa project 所需的用户库(vendor: EclipseLink)

    eclipse 构建 jpa project 所需的用户库(vendor: EclipseLink)

    Eclipse 构建 JPA Project 时,需要指定 JPA的实现,如:下图中的EclipseLink 2.7.3,这其实是一个自定义的用户库。看看,这个用户库包含persistence接口和eclipselink提供的实现。上述的用户库包含的jar包都在下面的压缩包中:EclipseLink_2.7.3.rar附:不过,我更喜欢直接用maven...

    2024-03-01 11:56:21
  • 数字滤波器基础学习

    数字滤波器基础学习

    一、数字滤波器的结构特点与表示方法数字滤波器是数字信号处理的一个重要组成部分。数字滤波实际上是一种运算过程,其功能是将一组输入的数字序列通过一定的运算后转变为另一组输出的数字序列,因此它本身就是一台数...

    2024-03-01 11:56:11
  • Java zip/gzip文件压缩和解压缩

    Java IOJAVA IO 支持的三种压缩格式:zip、gzip、jar。压缩文件@Test public void testZip() throws IOException { File zipFile = new File(&quot;D:\\log.zip&quot;); //压缩后的文件 ZipOutputStream zipOut = null; try{ zipOut

    2024-03-01 11:56:02
  • React全家桶(技术栈)

    第1章:React入门 1.1. React简介 1.1.1. 官网 英文官网: https://reactjs.org/ 中文官网: https://react.docschina.org/ 1.1...

    2024-03-01 11:55:52
  • 全国计算机等级考试试题研究组,全国计算机等级考试题研究中心

    全国计算机等级考试试题研究组,全国计算机等级考试题研究中心

    《全国计算机等级考试系列辅导用书?全国计算机等级考试笔试真题及近期新模拟试卷:二级C++语言(2012年考试专用)(含公共基础知识)》:天合教育网,人气旺的IT教育和技术社区,专家准确解析,详尽易懂,...

    2024-03-01 11:53:31
  • 数据结构——从英文字典树到中文字典树

    昨天面试电话中的一道题,题目如下:给你一个姓名的集合,查找你的名字是否在里面出现,比如搜索姓氏为叶的人,那么会出现所有姓为叶的人,应该如何设计?当时的回答是,姓为key,名为value,存放到multimap中,使用multimap中的count函数统计key为叶的个数,然后用find函数找到第一个key为叶的指针,使用迭代器从该指针向后查找count个元素,判断这count个元素中是否有姓名

    2024-03-01 11:53:24
  • h5物体拖动_HTML5中的拖放事件(Drag 和 drop)

    浏览器支持Internet Explorer 9、Firefox、Opera 12、Chrome 以及 Safari 5 支持拖放。注释:在 Safari 5.1.2 中不支持拖放。HTML5 拖放实...

    2024-03-01 11:53:15
  • 力扣 450. 删除二叉搜索树中的节点

    力扣 450. 删除二叉搜索树中的节点

    力扣 450. 删除二叉搜索树中的节点

    2024-03-01 11:50:14