Find the sequence in an array with largest sum

Problem: For any given input of numbers, find the maximum sum in a range (x, y| x<=y), the sum is defined as (A[i]+ A[i+1] + … + A[j]) where x<=i<=j<=y.
This problem can be solved by greedy algotithm:

1. public class LargestSequence {
2.     public static void main(String[] args) {
3.         int[] arr = { -3, -4, 3, 2, 5, -6, 3, 5, 1, -3, -2, -90, 10 };
4.         Interval result = findLargestSequence(arr);
5.         System.out.println(result);
6.     }
7.     /*
8.      * For any given input of numbers, find the maximum sum in a range (x, y| x<=y),
9.      * the sum is defined as (A[i]+ A[i+1] + … + A[j]) where x<=i<=j<=y.
10.      * @param the input array. element in array can be either posivie or negative.
11.      */
12.     public static Interval findLargestSequence(int[] arr) {
13.         if (arr == null || arr.length == 0) {
14.             return null;
15.         }
16.         Interval curr_interval = new Interval(0, 0);
17.         Interval max_interval = new Interval(0, 0);
18.         int max_sum = arr[0];
19.         int curr_sum = arr[0];
20.         for (int i = 1; i < arr.length; i++) {
21.             curr_sum += arr[i];
22.             curr_interval.y = i;
23.             if (curr_sum > max_sum) {
24.                 max_sum = curr_sum;
25.                 max_interval.x = curr_interval.x;
26.                 max_interval.y = curr_interval.y;
27.             }
28.             if (curr_sum < 0) {
29.                 curr_interval.x = i + 1;
30.                 curr_sum = 0;
31.             }
32.         }
33.         return max_interval;
34.     }
35.     static class Interval {
36.         int x;
37.         int y;
38.         int max_sum;
39.         Interval(int x, int y) {
40.             this.x = x;
41.             this.y = y;
42.         }
43.         @Override
44.         public String toString() {
45.             return “(” + this.x + “, ” + this.y + “)”;
46.         }
47.     }
48. }