To find a max segment in a array which includes negative and positive no.There r several methods to solve this question.And in the works, ignore the zero position.
1
package com.ibm.nicky.maxsegment;
2
3
/** *//**
4
* @author QuQiang
5 *
6 * The program can calculate the max sum segment
7 * source[i]+source[i+1]+…+source[j]in source array,and return the
8 * position.Ignore the zero position.
9
*/
10public class MaxSegment 
{
11
12
/** *//**
13 * if start = -1 end = -1 is returned, the array should be initialized
14
*/
15 private static int start = -1;
16 private static int end = -1;
17 private static int sum = 0;
18
19 private static int[] source = {-1,-2,-1,-10,-3,0,2,6,12,-5,6,-4};
20
21 /**//*
22 * The main function to test the method.
23 */
24/**//* public static void main(String[] args) {
25 System.out.println(MaxSegment.getThrOptimizedMaxSegment()
26 + ":" + MaxSegment.start + ":" + MaxSegment.end);
27 }*/
28
29 /** *//**
30 * @return the sum of the max segment but the method is not very nice. the
31 * algorithmic complexity is T(n)=O(n^3)
32 */
33 public static int getMaxSegment() {
34 start = -1;end = -1;sum = 0;
35 for (int i = 0; i < source.length; i++) {
36 for (int j = i + 1; j < source.length; j++) {
37 int temp = 0;
38 for (int k = i; k < j; k++) {
39 temp += source[k];
40 }
41 if (temp > sum) {
42 sum = temp;
43 start = i;
44 end = j - 1;
45 }
46 }
47 }
48 return sum;
49 }
50
51 /** *//**
52 * @return the sum of the max segment && use the previous result
53 * sum[i+1]=sum[i]+source[i+1]. algorithmic complexity is (n)=O(n^2)
54 */
55 public static int getFirOptimizedMaxSegment() {
56 start = -1;end = -1;sum = 0;
57 for (int i = 0; i < source.length; i++) {
58 int temp = 0;
59 for (int j = i; j < source.length; j++) {
60 temp += source[j];
61 if (temp > sum) {
62 sum = temp;
63 start = i;
64 end = j;
65 }
66 }
67 }
68 return sum;
69 }
70
71 /** *//**
72 * @return the sum of the max segment && use the recursion
73 * formula.Division-and-Conquer and Recursion algorithm algorithmic
74 * complexity is T(n)=2T(n/2)+O(n),T(n)=O(nlogn).
75 */
76 public static int getSecondOptimizedMaxSegment(int leftend, int rightend) {
77 start = -1;end = -1;sum = 0;
78 int centerpiont = 0, leftsum = 0, rightsum = 0;// ,tempstart = -1
79 // ,tempend = -1;
80 if (leftend == rightend)
81 sum = source[leftend] > 0 ? source[leftend] : 0;
82 else {
83 centerpiont = (leftend + rightend) / 2;
84 leftsum = getSecondOptimizedMaxSegment(leftend, centerpiont);
85 rightsum = getSecondOptimizedMaxSegment(centerpiont + 1, rightend);
86 }
87 int templeftSum = 0, lefts = 0;
88 for (int i = centerpiont; i > leftend - 1; i--) {
89 lefts += source[i];
90 if (lefts > templeftSum) {
91 templeftSum = lefts;
92 // tempstart = i;
93 start = i;
94 }
95 }
96 int temprightSum = 0, rights = 0;
97 for (int j = centerpiont + 1; j < rightend + 1; j++) {
98 rights += source[j];
99 if (rights > temprightSum) {
100 temprightSum = rights;
101 // tempend = j;
102 end = j;
103 }
104 }
105 sum = templeftSum + temprightSum;
106 if (sum < leftsum) {
107 start = leftend;
108 end = centerpiont;
109 return sum = leftsum;
110 } else if (sum < rightsum) {
111 start = centerpiont + 1;
112 end = rightend;
113 return sum = rightsum;
114 } else {
115 // start = tempstart ;
116 // end = tempend;
117 return sum;
118 }
119 }
120
121 /** *//**
122 * @return the sum of the max segment && use the dynamic programming
123 * (DP).temp[i]=max(temp[i-1]+source[i],source[i]) algorithmic
124 * complexity is O(n).(Not all are negative)
125 */
126 public static int getThrOptimizedMaxSegment() {
127 start = -1;end = -1;sum = 0;
128 int temp = 0;
129 int flag=-1, count=0;
130 for (int i = 0; i < source.length; i++) {
131 if (temp > 0){
132 temp += source[i];
133 flag = i;
134 count++;
135 }
136 else
137 temp = source[i];
138 if (temp > sum){
139 sum = temp ;
140 start = flag-count;
141 end = i;
142 }
143 }
144 return sum;
145 }
146
147 public static int getStart() {
148 return start;
149 }
150
151 public static int getEnd() {
152 return end;
153 }
154}