leetcode Maximum Subarray
1697 ワード
タイトルリンク
JAvaの悲しみは、線形時間でも通じない.いつもタイムアウトです.だから私はc++を1つ写して提出するしかありません.実はjavaで書いた答えもタイムアウトした人がいるので、言葉が間違っているとしか言えません.
構想:record配列.だからiまで記録して、前の連続の最大和.0より小さい場合は直接0と表記し、前の和が負であるため、必ず減少することを表す.
JAvaの悲しみは、線形時間でも通じない.いつもタイムアウトです.だから私はc++を1つ写して提出するしかありません.実はjavaで書いた答えもタイムアウトした人がいるので、言葉が間違っているとしか言えません.
構想:record配列.だからiまで記録して、前の連続の最大和.0より小さい場合は直接0と表記し、前の和が負であるため、必ず減少することを表す.
public class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==0)
{
return 0;
}
int record[]=new int[nums.length];
int max=0;
if(nums[0]>0)
{
record[0]=nums[0];
}
for(int i=1;i<nums.length;i++)
{
record[i]=Math.max(0, record[i-1]+nums[i]);
if(max>record[i])
{
max=record[i];
}
}
return max;
}
}