最大字串和问题(Maximum Subarray)
2024-09-03 17:28:40
问题描述：
ind the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
public class MaxSubarray
{
public int maxSubArray(int[] nums)
{
int sum = nums[0];
int max = nums[0];
for(int i = 1; i < nums.length; i ++)
{
if(sum < 0)
{
sum = 0;
}
sum += nums[i];
if(max < sum)
{
max = sum;
}
}
return max;
}
//穷举法O(n^3)
public int maxSubArray1(int[] nums)
{
int max = 0;
for(int i = 0; i < nums.length; i ++)
{
for(int j = i; j < nums.length; j ++)
{
int sum = 0;
for(int k = i; k < j; k ++)
{
sum += nums[k];
}
if(sum > max)
{
max = sum;
}
}
}
return max;
}
//O(n^2)
public int maxSubArray2(int[] nums)
{
int max = 0;
for(int i = 0; i < nums.length; i ++)
{
int sum = 0;
for(int j = i; j < nums.length; j ++)
{
sum += nums[j];
if(sum > max)
{
max = sum;
}
}
}
return max;
}
}
最新文章
- include使用中注意的问题
- 在CentOS 7上安装Node.js的4种方法
- Java基础(30):String对象的常用方法与实例（String类）
- struct和class 区别
- Linux - 简明Shell编程07 - 数组（Array）
- Beta Scrum
- kdump简单的介绍
- Selenium 笔记
- Harmonic Number (II) LightOJ - 1245 （找规律？。。。）
- 初探和实现websocket心跳重连(npm: websocket-heartbeat-js)
- 如何进行CodeReview
- winform菜单栏、工具栏
- Java图形处理
- 009.MySQL-Keepalived搭配脚本03
- Java并发（十四）：并发工具类——CountDownLatch
- clr via c#读书笔记五：常量和字段
- 【斜率优化】bzoj3675-[Apio2014]序列分割&&Uoj104
- (转)python学习链接
- Swing要点
- 卸载重安firefox