首页 > 代码库 > 最长子序列问题 最详细的解题报告

最长子序列问题 最详细的解题报告

最长子序列之和问题

 

算法一:暴力法(时间复杂度:O(N^2))

算法描述:依次求从j到i中最大的和,并将最大的和记录在maxValue中,容易理解但是效率低。

 

 1 static int MaxSum1(int[] arr) { 2         int maxValue = http://www.mamicode.com/Integer.MIN_VALUE; 3         for (int i = 0; i < arr.length; i++) { 4             int curSum = 0; 5             for (int j = 0; j <= i; j++) { 6                 curSum += arr[j]; 7                 if (curSum > maxValue) { 8                     maxValue =http://www.mamicode.com/ curSum; 9                 }10             }11         }12         return maxValue;13     }

 

算法二:分治法(时间复杂度:O(NlogN))

算法描述:将整个序列分成两部分,序列最大和有三种情况:

1、在左边子序列中;

2、在右边子序列中;

3、一部分在做序列中,另一部分在有序列中,但是该序列一定包含左子序列的最后一个元素mid,和又子序列的第一个元素mid+1。

 

对于第1、2中情况,直接递归就可以了;对于第3中情况,需要从左子序列的mid出发,依次递减,求得最大值midLeftSum,再从右子序列的第一个元素mid+1出发,依次递增,求得最大值midRightSum,最后要求的值为:midLeftSum+midRightSum。

 

整个序列的最大和为第1、2和3中情况中的最大值。

 

 1 static int MaxSum2(int[] arr, int start, int end) { 2         int maxValue = http://www.mamicode.com/Integer.MIN_VALUE; 3         if (start == end) { 4             if (arr[start] > 0) { 5                 maxValue =http://www.mamicode.com/ arr[start]; 6             } 7         } else { 8             int mid = (start + end) / 2; 9             int leftMaxValue =http://www.mamicode.com/ MaxSum2(arr, start, mid);10             int rightMaxValue = http://www.mamicode.com/MaxSum2(arr, mid + 1, end);11 12             int midLeftMaxValue = http://www.mamicode.com/0;13             int midLeftSum = 0;14             for (int i = mid; i >= 0; i--) {15                 midLeftSum += arr[i];16                 if (midLeftSum > midLeftMaxValue) {17                     midLeftMaxValue =http://www.mamicode.com/ midLeftSum;18                 }19             }20 21             int midRightMaxValue = http://www.mamicode.com/0;22             int midRightSum = 0;23             for (int i = mid + 1; i <= end; i++) {24                 midRightSum += arr[i];25                 if (midRightSum > midRightMaxValue) {26                     midRightMaxValue =http://www.mamicode.com/ midRightSum;27                 }28             }29             maxValue = http://www.mamicode.com/Math.max(leftMaxValue,    Math.max(rightMaxValue, midLeftMaxValue    + midRightMaxValue));30         }31         return maxValue;32     }

 

算法三:动态规划(时间复杂度:O(N))

算法描述:首先我们想一下,要想为最大子序列之和做贡献,该元素一定要大于0,所以如果第i个子序列之前的子序列之和小于0,就应该舍去。(我当时理解了很长时间才理解清楚)

 

 1 static int MaxSum3(int[] arr) { 2         int maxValue =http://www.mamicode.com/ Integer.MIN_VALUE; 3         int curSum = 0; 4         for (int i = 0; i < arr.length; i++) { 5             curSum+=arr[i]; 6             if (curSum > maxValue) { 7                 maxValue =http://www.mamicode.com/ curSum; 8             } 9             if(curSum<0){ //第i以前的子序列为做出贡献,小于0,应该舍去10                 curSum=0;11             }12         }13         return maxValue;14     }

最长子序列问题 最详细的解题报告