h********8
发帖数: 1 | 1 请教Leetcode Maximum Subarray 如果加两个条件，怎么解：
1. 打印Start和End，这个比较容易。
2. 返回的Subarray的长度要大于1。（追问如果是大于N呢？）
以下是我的大于1的code，各位有没有更好的解法？
public int maxSubWithSizeGreaterThanOne(int[] nums) {
if (nums.length < 2) {
return 0;
}
int maxStart = 0;
int maxEnd = 1;
int start = 0;
int sum = nums[0] + nums[1];
int max = sum;
for (int i=2; i
sum = Math.max(sum+nums[i], nums[i-1]+nums[i]);
if (sum == nums[i-1]+nums[i]) {
start = i-1;
}
max = Math.max(max, sum);
if (max == sum) {
maxStart = start;
maxEnd = i;
}
}
System.out.println("start and end are " + maxStart + " " + maxEnd);
return max;
} |
b*****n
发帖数: 618 | 2 可以继续用DP吧，加个维度就好，subarray的长度 |
m******3
发帖数: 346 | 3 这个DP怎么写呢？
定义dp[i][j]为以nums[i]结尾的长度为j的subArray长度
dp[i][1] = nums[i]
dp[i][j] = (dp[i-1][j-1]+nums[i]) if dp[i-1][j-1]!=0;
dp[i][j] = 0; if dp[i-1][j-1]=0
是这样么 ？ |
b*****n
发帖数: 618 | 4 貌似也不用。。
只要算一下每个长度为n的以nums[i]结尾的最大值，然后dp长度为>=n的以nums[i]结尾
的最大值就行了，这样线性就能解决。
最开始的largest subarray sum其实是n==1的一种特殊情况，做法是完全一样的。
【在 m******3 的大作中提到】
: 这个DP怎么写呢？
: 定义dp[i][j]为以nums[i]结尾的长度为j的subArray长度
: dp[i][1] = nums[i]
: dp[i][j] = (dp[i-1][j-1]+nums[i]) if dp[i-1][j-1]!=0;
: dp[i][j] = 0; if dp[i-1][j-1]=0
: 是这样么 ？
|
m******3
发帖数: 346 | 5
【在 b*****n 的大作中提到】
: 貌似也不用。。
: 只要算一下每个长度为n的以nums[i]结尾的最大值，然后dp长度为>=n的以nums[i]结尾
: 的最大值就行了，这样线性就能解决。
: 最开始的largest subarray sum其实是n==1的一种特殊情况，做法是完全一样的。
|
m******3
发帖数: 346 | 6 没有太明白，算一下每个长度为n的以nums[i]结尾的最大值，如何线性解决？
也是DP么？ 另外我觉得和n=1的情况还是有区别的啊，如果subarray是从nums[i]开始
而不是在已经有的subArray上加上nums[i],对n=1的情况没问题，nums[i]本身就保证了
长度至少大于等于1,但是如果n!=1,这个没办法保证吧，能详细说说么？
【在 b*****n 的大作中提到】
: 貌似也不用。。
: 只要算一下每个长度为n的以nums[i]结尾的最大值，然后dp长度为>=n的以nums[i]结尾
: 的最大值就行了，这样线性就能解决。
: 最开始的largest subarray sum其实是n==1的一种特殊情况，做法是完全一样的。
|
b*****n
发帖数: 618 | 7
这是个sliding window吧
sum[i]表示nums[i]结尾的长度为n的subarray sum
sum[i] = sum[i - 1] - nums[i - n] + nums[i]
dp[i]表示nums[i]结尾的长度>=n的subarray sum最大值
dp[i] = max(sum[i], dp[i - 1] + nums[i])
【在 m******3 的大作中提到】
: 没有太明白，算一下每个长度为n的以nums[i]结尾的最大值，如何线性解决？
: 也是DP么？ 另外我觉得和n=1的情况还是有区别的啊，如果subarray是从nums[i]开始
: 而不是在已经有的subArray上加上nums[i],对n=1的情况没问题，nums[i]本身就保证了
: 长度至少大于等于1,但是如果n!=1,这个没办法保证吧，能详细说说么？
|
m******3
发帖数: 346 | |
