我用的brute force，非最优解，通不过。204/209 cases passed，反馈只给了正确答案，好像是数列比较长，数比较大的时候不对。但我不知道哪里错了。大牛们帮看看，指点一下吧 题目：Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array. Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
class Solution { public int maxSubArray(int[] nums) { int largest = Integer.MIN_VALUE; if (nums.length == 0) { return largest; } if (nums.length == 1) { return nums[0]; } for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; largest = Math.max(sum, largest); } } return largest; } }
class Solution { public int maxSubArray(int[] nums) { int largest = Integer.MIN_VALUE; if (nums.length == 0) { return largest; } if (nums.length == 1) { return nums[0]; } for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; largest = Math.max(sum, largest); } } return largest; } }
好啊 新年新气象
直接看答案吧，这个估计要DP
嗯，就是基本上不要搞两个for loop
这题是基本的DP课后题啊
如果没报超时, 只是报错, 那确实有可能是overflow。你那个sum在变负的时候, 不能一直负下去, 必须要清成0的。看答案吧。
对头
好几年没刷的飘过
203 / 209 test cases passed. Status: Time Limit Exceeded
int findMaxSubarray(vector<int> array) { int currMax = array[0]; int currTailMax = array[0]; for (int i = 1; i < array.size(); i++) { if (array[ i ] > currTailMax) { currTailMax = array[ i ]; } else { currTailMax += array[ i ]; } if(currTailMax > currMax) { currMax = currTailMax; } } return currMax; }
谢谢，我是在VSCode里面直接提交的，没去Leetcode网站，没有看到超时的信息。下次再到网站提交试试
刷题是为了练习学到的算法知识和解题技巧。这个楼主DP还没弄明白,为啥要把时间花在naive解上？浪费时间!还跑到华人上来问,好玩儿么？
对
for (int i = 1; i < n; i++) { currentSum = Math.max(currentSum + array[ i ], array[ i ]); maxSubSum = Math.max(maxSubSum, currentSum); }
array [ i ] 发不出来
我的答案是请不要把时间浪费在写naive的解和弄清naive的解过不了上面。请把时间用来学习正确的高效的解法。
把正确高效的解法套路积累到一定程度之后,再开始想办法自己解题。
你这样搞好比只学了加法却要计算乘法,99表都没背清楚,算个8x8也只能把8个8拿来手动相加。有意义么？