一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和,求所有子数组的和的最大值
下面是一个效率很低的方法两层循环,思路是分别以每一个元素为起点,定义一个temp值保存现有的最大和,如果遍历到的连续子数组的和大于temp那么则交换两者的值。
import java.util.*;
class BigChild
{
public static void main(String[] args)
{
int temp=0;
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
String[] st=str.split(",");
int[] arr=new int[st.length];
for(int i=0;i<st.length;i++)
{
arr[i]=new Integer(st[i]);
}
for(int i=0;i<arr.length;i++)
{
//sum一定要在这里定义,否则会变成一个累加值
int sum=0;
for(int j=i;j<arr.length;j++)
{
sum+=arr[j];
if(sum>temp)
temp=sum;
}
}
System.out.println(temp);
}
}
下面是一个只有一层循环的算法
思路是若temp<sum,则sum保持原值。
import java.util.*;
class BigChild
{
public static void main(String[] args)
{
int temp=0;
int sum=0;
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
String[] st=str.split(",");
int[] arr=new int[st.length];
for(int i=0;i<st.length;i++)
{
arr[i]=new Integer(st[i]);
}
for(int i=0;i<arr.length;i++)
{
if(temp<0)
temp=arr[i];
else
temp+=arr[i];
if(temp>sum)
sum=temp;
}
System.out.println(sum);
}
}
分享到:
相关推荐
求一个数组子数组的最大和,这是一道非常经典的公司面试或笔试题目,我分别使用了暴力枚举、分枝界定、动态规划三种算法实现。
5.8 寻找最大连续子序列 5.9 增强归纳假设 5.10 动态规划:背包问题 5.11 常见的错误 5.12 小结 第6章 序列和集合的算法 6.1 引言 6.2 二叉搜索的几种形式 6.2.1 纯二叉搜索 6.2.2 循环序列的二叉搜索 ...
这些结点的物理地址不一定是连续的,即可能连续,也可能不连续,但链表里的结点是有序的。一个结点由数据的值和下一个数据的地址组成。一个链表内的数据类型可以是多种多样的。数组也是用来存储数据的,与链表相比,...
该算法的主要思想是在每一步将给定的排序数组 A 划分为两个子数组,并在两个子数组之一中查找关键元素 K。 (您可以阅读代码“BinarySearch.ipynb” // 记录和评论的所有内容。 :bookmark: 线性搜索: 在这种搜索...
滑动窗口:连续子数组、子串 两个指针:三元和 Tree BFS:面向水平的数学,水平关系 树 DFS : 一些准备方法 策略 1(掌握):一次一个主题。 即要使用链表,解决所有与链表相关的问题 策略 2(暴露):为问题设计一...
可设一个数组DIST(X)来表示节点X与原点v0之间的距离,S和V-S分别表示目前暂确定找到最短路径节点的集合与未确定最短路径节点集合,初始时S仅包含v0源点,算法结束时S应包含所有节点。 Dijkstra算法的步骤如下: **...
二叉树的创建与遍历 满二叉树:在满二叉树中...堆:堆是一种特殊的二叉树,其中父节点的值总是大于或等于子节点的值(最大堆)或小于或等于子节点的值(最小堆)。堆在优先队列、Dijkstra算法等场景中有着广泛的应用。
在下列两种情况下也只能采用顺序查找: ①如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,只能用顺序查找; ②即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。 1.7.2 二分法查找 二分法...
一般情况下演示屏由图示、算法和变量三个窗口组成,特殊情况下将根据演示内容适当增加。一般情况下, 左侧图示窗口显示演示数据的逻辑结构或存储结构,右侧上方窗口显示算法文本,右侧下方窗口显示当前算法中各变量...
一般情况下演示屏由图示、算法和变量三个窗口组成,特殊情况下将根据演示内容适当增加。一般情况下, 左侧图示窗口显示演示数据的逻辑结构或存储结构,右侧上方窗口显示算法文本,右侧下方窗口显示当前算法中各变量...
的子数组之和 使用 Brian Kernighan 的算法 O(n) 对所有数字进行按位与 LRU缓存 跳跃游戏 最长公共子序列 最大平方 第一个唯一编号 二叉树最大路径和 二叉树中的根到叶路径 第一个坏版本 珠宝和石头(基于套装的
leetcode中国 code_algo ...给定一个整数数组nums,找到一个具有最大和的连续子数组(至少一个元素),返回其和 最长公共子序列(Longest Common Subsequence,简称 LCS)是一道非常经典的面试题目, 因为它的
<br>实验二 单链表结构及计算 实验目的: 通过实验掌握下列知识: 1、熟悉线性表的基本运算在两种存储结构(顺序结构和链式结构)上的实现; 2、继续熟悉VC编程、编译和调试环境; 内容及步骤:...
这适用于需要遍历元素列表的问题,在这些元素中,您必须从具有大小为k个元素的连续元素的子数组中搜索或计算某些内容。 测试场景: 给定一个数组,找到大小为k的所有子数组的平均值。 输入:arr = [1、3、2、6,-...
基于JAVA的UDP服务器模型源代码,内含UDP服务器端模型和UDP客户端模型两个小程序,向JAVA初学者演示UDP C/S结构的原理。 简单聊天软件CS模式 2个目标文件 一个简单的CS模式的聊天软件,用socket实现,比较简单。 ...
1、从弹框中,分两次输入两个数字,分别保存在 a 和 b中 2、如果 a 大于 b的话 ,则交换两个数字的位置 使用 短路&&,扩展赋值运算符,位运算 4、条件运算符(三目运算) 单目(一元)运算符 :++,--,! 双目(二元)...
6.数据结构中评价算法的两个重要指标是(时间复杂度和空间复杂度) 【北京理工大学 2001 七、1(2分)】 7. 数据结构是研讨数据的_(1)物理结构_和_(2)逻辑结构 _,以及它们之间的相互关系,并对与这种结构定义...
前一章涵盖基本概念、代表性算法和评估技术,而后一章讨论高级概念和算法。这样读者在透彻地理解数据挖掘的基础的同时,还能够了解更多重要的高级主题。目录封面 -16封底 -15扉页 -14版权 -13版权声明 -12中文版序 -...
2. LOG算子:是高斯和拉普拉斯的双结合,即集平衡(高斯算子,高斯滤波)和边沿(拉普拉斯算子是二阶导求边缘)。这类似于各向异性滤波器(这是高斯一阶导函数),而LOG可以看做是二阶导函数。这两模型来源最初都是...