int array[] = {-1, 4, -2, 5, -5, 2, -20, 6};
如果我有那个数组,我的Kadane算法实现找到最大的子数组工作:
int max_so_far = INT_MIN;
int max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max(max_ending_here + array[i], 0);
max_so_far = max(max_ending_here, max_so_far);
}
printf("%d\n", max_so_far);
但是,如果我有一个所有负数的数组:
int array[]= {-10, -10, -10};
它不起作用,它应该返回-10,但我得到0.
我怎样才能让它对负数起作用？
谢谢!
我正在尝试找到关于子阵列最小切片的编码问题的解决方案,并且我已经设计了一个使用Kadane算法的修改版本的解决方案.我目前已经获得90/100并且设法通过O(n)中的几乎所有测试.但是,我似乎无法通过"medium_range,增加,减少(legth = ~100)和小功能,得到5预期3",我不知道为什么.这可能是解决方案的重复,但我使用的方法略有不同.
我的逻辑如下:
a)如果我们有一个数组MinA,其中MinA [k]表示从k开始的子阵列的最小平均切片,最小长度为2
b)然后,如果我们循环通过MinA并找到数组的最小值,那么这将是整个数组的最小平均切片(然后返回索引位置)
c)创建这个MinA,我们从数组的倒数第二个元素开始,MinA [A.length -2]是A的最后两个元素的平均值
d)我们将柜台向左移动一个位置; MinA [计数器]必须是A [计数器]和A [计数器+ 1]的平均值或元素计数器的平均值和MinA [counter + 1]中的元素
e)如果d不为真,那么这意味着MinA [counter + 1]不是从计数器+ 1到从计数器+ 2到N的某个元素的最小平均切片
我想知道我是否遗漏了什么？
/*
* Using modified version of Kadane's algorithm
* The key logic is that for an array A of length N,
* if M[k + 1] is the minimum slice of a subarray from k + 1 to any element
* between k+2 to n, then M[k] is either the …给定具有+ ve和-ve整数的数组,找到最大总和,以便不允许跳过2个连续元素(即,您必须选择其中至少一个向前移动).
例如: -
10,20,30,-10,-50,40,-50,-1,-3
输出:10 + 20 + 30-10 + 40-1 = 89
以下是一个名为codility的编码访谈网站的演示问题:
字符串S的前缀是S的任何前导连续部分.例如,"c"和"cod"是字符串"codility"的前缀.为简单起见,我们要求前缀非空.
字符串S的前缀P的乘积是P的出现次数乘以P的长度.更准确地说,如果前缀P由K个字符组成并且P在S中恰好出现T次,那么乘积等于K*T.
例如,S ="abababa"具有以下前缀:
- "a",其产品等于1*4 = 4,
- "ab",其产品等于2*3 = 6,
- "aba",其产品等于3*3 = 9,
- "abab",其产品等于4*2 = 8,
- "ababa",其产品等于5*2 = 10,
- "ababab",其产品等于6*1 = 6,
- "abababa",其产品等于7*1 = 7.
最长的前缀与原始字符串相同.目标是选择这样的前缀以最大化产品的价值.在上面的例子中,最大乘积是10.
以下是我在Java中的糟糕解决方案,需要O(N ^ 2)时间.显然可以在O(N)中执行此操作.我在考虑Kadanes算法.但我想不出任何可以在每个步骤编码某些信息的方法,让我找到运行的最大值.任何人都可以为此考虑O(N)算法吗？
import java.util.HashMap;
class Solution {
public int solution(String S) {
int N = S.length();
if(N<1 || N>300000){
System.out.println("Invalid length");
return(-1);
}
HashMap<String,Integer> prefixes = new HashMap<String,Integer>();
for(int i=0; i<N; i++){
String keystr = "";
for(int j=i; j>=0; j--) {
keystr += S.charAt(j);
if(!prefixes.containsKey(keystr))
prefixes.put(keystr,keystr.length());
else{
int newval = prefixes.get(keystr)+keystr.length();
if(newval …你有没有觉得你的脑袋不适合算法？
我尝试解决最大子数组问题，并且在 Codewars 上遇到了这个解决方案：
var maxSequence = function(arr){
var min = 0, ans = 0, i, sum = 0;
for (i = 0; i < arr.length; ++i) {
sum += arr[i];
min = Math.min(sum, min);
ans = Math.max(ans, sum - min);
}
return ans;
}
console.log(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, -4]));我了解如何使用线性时间复杂度解决这个问题Kadane's algorithm：
var maxSequence = function(arr){
let max = 0;
let localMax = 0;
for (let i = 0; i …我在javascript中实现了Kadane的Max Sub数组问题,但似乎我最终总是在控制台中得到0,即使存在更高的数字(我知道它做了它正在做的事情因为for循环从0 - size哪里size = subarray size).
那么我该如何正确实现算法呢？
它是否也适用于所有正整数数组？
我正在尝试编写一个程序来解决最大的子阵列问题.我可以理解Kadane算法在1-D阵列上的直觉以及2-D阵列上的O(N ^ 4)实现.但是,我在理解二维阵列上的O(N ^ 3)实现时遇到了一些麻烦.
1)为什么我们将元素与同一列中前一行的元素相加？
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
array[i][j] += array[i-1][j];
}
2)我不了解算法的第二部分
试图在网上寻找解释但无济于事.希望在这里得到一些帮助!
提前致谢!
为了使动态规划适用，问题必须具有两个关键属性：最优子结构和重叠子问题 [1]。对于这个问题，我们将只关注后一个属性。
重叠子问题有多种定义，其中两个是：
如果找到解决方案涉及多次解决相同的子问题，那么这两个定义（以及互联网上的许多其他定义）似乎都可以归结为具有重叠子问题的问题。换句话说，在寻找原始问题的解决方案的过程中，有许多小的子问题被多次计算。一个经典的例子是斐波那契算法，很多例子都用来让人们理解这个属性。
直到几天前，生活都很棒，直到我发现了Kadane 的算法，这让我质疑重叠的子问题定义。这主要是因为人们对它是否是 DP 算法有不同的看法：
有人不认为 Kadane 的算法是 DP 算法的最令人信服的原因是每个子问题只会在递归实现中出现和计算一次[3]，因此它不包含重叠子问题的属性。然而，互联网上的很多文章都认为 Kadane 的算法是一种 DP 算法，这让我怀疑我对重叠子问题的理解首先意味着什么。
人们似乎对重叠子问题的属性有不同的解释。使用简单的问题（例如斐波那契算法）很容易看到它，但是一旦您介绍了 Kadane 的算法，事情就会变得非常不清楚。如果有人能提供一些进一步的解释，我将不胜感激。
algorithm dynamic-programming fibonacci divide-and-conquer kadanes-algorithm
我一直在解决算法简介 - CLRS中的练习，并遇到了在线性时间内求解最大连续子数组的问题（Q 4.1-5）。请看下面我的解决方案。我一直在网上寻找这项练习的评委，但没有找到。解决这个问题后，当我寻找解决方案时，我发现 kadane 的算法似乎与我的实现不同，而且当所有数字均为负数时，该解决方案也会给出正确的输出。
public static int linearMaxSolve(int[] arr) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int i : arr) {
sum += i;
if (i > sum) {
sum = i;
}
if (sum > max) {
max = sum;
}
}
return max;
}
除了向程序输入手动测试用例之外，还有其他方法可以检查该算法的有效性吗？