【剑指offer】30连续子数组的最大和
数组 最大 30 Offer 连续
2023-09-11 14:20:18 时间
/**
*题目描述:
*HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。
*今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,
*当向量全为正数的时候,问题很好解决。
*但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?
*例如:{6,-3,-2,7,-15,1,2,2},
*连续子向量的最大和为8(从第0个开始,到第3个为止)。
*你会不会被他忽悠住?(子向量的长度至少是1)
*/
import java.util.*;
public class Solution {
//动态规划
public int FindGreatestSumOfSubArray(int[] array) {
int result=array[0]; //上次记录的最大值
int tmp=array[0]; //本次记录的最大值
for (int i=1;i<array.length;i++ ) {
tmp=Math.max(tmp+array[i],array[i]);
result=Math.max(tmp,result);
}
return result;
}
public static void main(String[] args) {
Solution s=new Solution();
int[] array={6,-3,-2,7,-15,1,2,2};
System.out.println(s.FindGreatestSumOfSubArray(array));
}
}
相关文章
- 面试题:二维数组排序
- js条件语句之职责链数组
- 【华为OD机试真题 python】最大平分数组【2022 Q4 | 200分】
- 【算法】【字符串模块】重新排列字符串数组使得字符串数组整体顺序最小或最大
- 【算法】【二叉树模块】判断数组是否能够重建搜索二叉树并实现重建搜索二叉树的过程
- 242. 一个简单的整数问题【树状数组 区间加 单点和】
- C++ 数组
- [算法]最大连续子数组和,最长重复子串,最长无重复字符子串
- JS中数组随机排序实现(原地算法sort/shuffle算法)
- 【C语言】零长度数组(可变数组,柔性数组)
- Swift - 数组排序方法(附样例)
- 剑指offer解法汇总4-二维数组中的查找
- 力扣解法汇总689-三个无重叠子数组的最大和
- LeetCode 421. 数组中两个数的最大异或值
- (第11列)C语言练习:输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组。五步带你解决。
- LeetCode215之数组中的第K个最大元素(相关话题:堆排序,快速排序,减治法)
- 200、【数组】leetcode ——6316. 重排数组以得到最大前缀分数(C++版本)
- 175、【动态规划】leetcode ——718. 最长重复子数组 (C++版本)
- 数组知识点
- 使用Array的原型使对象具有length,和数组的内容
- R语言基础题及答案(一)——数组、数据框、list列表的创建及部分基础问题
- Javascript : 数组
- PHP 修改数组中的值
- [LeetCode] 932. Beautiful Array 漂亮数组
- [LeetCode] Maximum Sum of 3 Non-Overlapping Subarrays 三个非重叠子数组的最大和
- [LeetCode] Maximum Average Subarray I 子数组的最大平均值
- [LintCode] Product of Array Except Self 除本身之外的数组之积
- PHP 十万数字不同数组取最大的5个 (经典面试题topK) (原)