例如,我们有
{2,2,-1},
when k = 0, return -1.
when k = 3, return 3.
由于我们有负数和一个额外的变量k,这个问题甚至更加棘手。k可以是任何值,包括负数,不要做任何假设。
我不能参考https://en.wikipedia.org/wiki/Maximum_subarray_problem 和https://www.youtube.com/watch?v=yCQN096CwWM 来解决这个问题。
有人能帮忙吗?最好使用Java或JavaScript。
这里是一个关于最大子数组问题的经典算法O(n),没有变量k:
public int maxSubArray(int[] nums) {
int max = nums[0];
int tsum = nums[0];
for(int i=1;i<nums.length;i++){
tsum = Math.max(tsum+nums[i],nums[i]);
max = Math.max(max,tsum);
}
return max;
}