05 August 2008
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int maxSum = nums[0], minSum = nums[0], pre1 = 0, pre2 = 0, arrSum = 0;
for (int num : nums) {
arrSum += num;
pre1 = Math.max(num, pre1 + num);
maxSum = Math.max(maxSum, pre1);
pre2 = Math.min(num, pre2 + num);
minSum = Math.min(minSum, pre2);
}
if (maxSum < 0) {
return maxSum;
}
return Math.max(arrSum - minSum, maxSum);
}
}
朴素DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// need modification
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int ans=nums[0],sum=nums[0],s=nums[0];
int dp[]=new int[nums.length];
dp[0]=nums[0];
for(int i=1;i<nums.length;i++)
{
sum=Math.max(sum+nums[i],nums[i]);
s=s+nums[i];
ans=Math.max(sum,ans);
dp[i]=Math.max(dp[i-1],s);
}
sum=0;
for(int i=nums.length-1;i>0;i--)
{
sum=sum+nums[i];
ans=Math.max(dp[i-1]+sum,ans);
}
return ans;
}
}