leetcode/MaximumSubarray.java at master · mengli/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Find the contiguous subarray within an array (containing at least one number) which has the
 * largest sum.
 *
 * <p>For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has
 * the largest sum = 6.
 *
 * <p>click to show more practice.
 *
 * <p>More practice: If you have figured out the O(n) solution, try coding another solution using
 * the divide and conquer approach, which is more subtle.
 */
publicclassMaximumSubarray {
publicintmaxSubArray(int[] A) {
intmax = Integer.MIN_VALUE;
intsum = 0;
for (inti = 0; i < A.length; i++) {
sum += A[i];
if (sum > max) {
max = sum;
 }
if (sum < 0) {
sum = 0;
 }
 }
returnmax;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Find the contiguous subarray within an array (containing at least one number) which has the
 * largest sum.
 *
 * <p>For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has
 * the largest sum = 6.
 *
 * <p>click to show more practice.
 *
 * <p>More practice: If you have figured out the O(n) solution, try coding another solution using
 * the divide and conquer approach, which is more subtle.
 */
publicclassMaximumSubarray {
publicintmaxSubArray(int[] A) {
intmax = Integer.MIN_VALUE;
intsum = 0;
for (inti = 0; i < A.length; i++) {
sum += A[i];
if (sum > max) {
max = sum;
 }
if (sum < 0) {
sum = 0;
 }
 }
returnmax;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Find the contiguous subarray within an array (containing at least one number) which has the
 * largest sum.
 *
 * <p>For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has
 * the largest sum = 6.
 *
 * <p>click to show more practice.
 *
 * <p>More practice: If you have figured out the O(n) solution, try coding another solution using
 * the divide and conquer approach, which is more subtle.
 */
publicclassMaximumSubarray {
publicintmaxSubArray(int[] A) {
intmax = Integer.MIN_VALUE;
intsum = 0;
for (inti = 0; i < A.length; i++) {
sum += A[i];
if (sum > max) {
max = sum;
 }
if (sum < 0) {
sum = 0;
 }
 }
returnmax;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Find the contiguous subarray within an array (containing at least one number) which has the
 * largest sum.
 *
 * <p>For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has
 * the largest sum = 6.
 *
 * <p>click to show more practice.
 *
 * <p>More practice: If you have figured out the O(n) solution, try coding another solution using
 * the divide and conquer approach, which is more subtle.
 */
publicclassMaximumSubarray {
publicintmaxSubArray(int[] A) {
intmax = Integer.MIN_VALUE;
intsum = 0;
for (inti = 0; i < A.length; i++) {
sum += A[i];
if (sum > max) {
max = sum;
 }
if (sum < 0) {
sum = 0;
 }
 }
returnmax;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Find the contiguous subarray within an array (containing at least one number) which has the
 * largest sum.
 *
 * <p>For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has
 * the largest sum = 6.
 *
 * <p>click to show more practice.
 *
 * <p>More practice: If you have figured out the O(n) solution, try coding another solution using
 * the divide and conquer approach, which is more subtle.
 */
publicclassMaximumSubarray {
publicintmaxSubArray(int[] A) {
intmax = Integer.MIN_VALUE;
intsum = 0;
for (inti = 0; i < A.length; i++) {
sum += A[i];
if (sum > max) {
max = sum;
 }
if (sum < 0) {
sum = 0;
 }
 }
returnmax;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Find the contiguous subarray within an array (containing at least one number) which has the
 * largest sum.
 *
 * <p>For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has
 * the largest sum = 6.
 *
 * <p>click to show more practice.
 *
 * <p>More practice: If you have figured out the O(n) solution, try coding another solution using
 * the divide and conquer approach, which is more subtle.
 */
publicclassMaximumSubarray {
publicintmaxSubArray(int[] A) {
intmax = Integer.MIN_VALUE;
intsum = 0;
for (inti = 0; i < A.length; i++) {
sum += A[i];
if (sum > max) {
max = sum;
 }
if (sum < 0) {
sum = 0;
 }
 }
returnmax;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Find the contiguous subarray within an array (containing at least one number) which has the
 * largest sum.
 *
 * <p>For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has
 * the largest sum = 6.
 *
 * <p>click to show more practice.
 *
 * <p>More practice: If you have figured out the O(n) solution, try coding another solution using
 * the divide and conquer approach, which is more subtle.
 */
publicclassMaximumSubarray {
publicintmaxSubArray(int[] A) {
intmax = Integer.MIN_VALUE;
intsum = 0;
for (inti = 0; i < A.length; i++) {
sum += A[i];
if (sum > max) {
max = sum;
 }
if (sum < 0) {
sum = 0;
 }
 }
returnmax;
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Find the contiguous subarray within an array (containing at least one number) which has the
 * largest sum.
 *
 * <p>For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has
 * the largest sum = 6.
 *
 * <p>click to show more practice.
 *
 * <p>More practice: If you have figured out the O(n) solution, try coding another solution using
 * the divide and conquer approach, which is more subtle.
 */
publicclassMaximumSubarray {
publicintmaxSubArray(int[] A) {
intmax = Integer.MIN_VALUE;
intsum = 0;
for (inti = 0; i < A.length; i++) {
sum += A[i];
if (sum > max) {
max = sum;
 }
if (sum < 0) {
sum = 0;
 }
 }
returnmax;
 }
}