Memoizationを使った解法
public int maxSubArray(int[] nums) {
int ans = nums[0];
int[] sumArray = new int[nums.length];
sumArray[0] = nums[0];
for(int i=1; i<nums.length; i++){
sumArray[i] = Math.max(nums[i], sumArray[i-1] + nums[i]);
ans = Math.max(ans, sumArray[i]);
}
return ans;
}
別解
public int maxSubArray(int nums[]) {
int size = nums.length;
int ans = Integer.MIN_VALUE;
int tempSubArraySum = 0;
for (int i = 0; i < size; i++) {
tempSubArraySum += nums[i];
if (ans < tempSubArraySum) {
ans = tempSubArraySum;
}
if (tempSubArraySum < 0) {
tempSubArraySum = 0;
}
}
return ans;
}
ここがよくわからなかった↓
if (tempSubArraySum < 0) {
tempSubArraySum = 0;
}