最大サブシーケンスの合計
1612 ワード
package com.alipay.math.base;
/**
*
*
* @author xu.le
*
*/
public class MaxSubsequenceSum {
static int seqStart=0;
static int seqEnd=0;
/**
* O(n )
* @param a
* @return
*/
public static int maxSubsequenceSum(int[] a){
int maxSum=0;//
for(int i=0;i<a.length;i++){
int tempSum=0;//
for(int j=i;j<a.length;j++){
tempSum+=a[j];
if(tempSum>maxSum){
maxSum=tempSum;
seqStart=i;
seqEnd=j;
}
}
}
return maxSum;
}
/**
* O(n)
* @param a
* @return
*/
public static int maxSubsequenceSumAdvance(int[] a){
int maxSum=0;
int tempSum=0;
int count=0;
for(int i=0,j=0;i<a.length;j++){
tempSum+=a[j];
if(tempSum>maxSum){
maxSum=tempSum;
if(count==0)
seqStart=i;
seqEnd=j;
count++;
}else {
if(tempSum<0)
tempSum=0;
}
i=j+1;
}
return maxSum;
}
public static void main(String args[]){
int[] i={-2,11,-4,13,-5,2};
int[] j={1,-3,4,-2,-1,6};
int maxSum=maxSubsequenceSumAdvance(i);
System.out.println("maxSum:"+maxSum);
System.out.println("seqStart:"+i[seqStart]);
System.out.println("seqEnd:"+i[seqEnd]);
}
}