package commonProblems;import java.util.*;public class MaxSubRun { int[] nums = new int[] {1,2,-3,2, 4,5,-6,7,-8,9,-3}; //int[] nums = new int[] {1, 98, -500, 2, 99, 2, -500, 3}; public static void main(String[] args){ MaxSubRun a = new MaxSubRun(); a.checkMaxRun(); } public void checkMaxRun(){ SubRun a = getMaxSubRun(0, nums.length - 1); System.out.println("run.. is " + a); } public SubRun getMaxSubRun(int start, int end){ SubRun maxRun; SubRun endRun; maxRun = new SubRun(start,start); endRun = maxRun; for(int i = start; i <= end; i++){ endRun = new SubRun(endRun.start, i); if(endRun.sum() < nums[i]){ //if just this one element is better than the whole // subrun so far, then discard the rest of it! endRun = new SubRun(i, i); } if(endRun.sum() > maxRun.sum()){ maxRun = endRun; } } return maxRun; } private class SubRun { public int start; public int end; private int max = 0; public SubRun(int start, int end){ if(start > end){ this.end = start; this.start = end; } else { this.start = start; this.end = end; } } public SubRun(){ max = 1; } public int sum(){ //allows for easier updating //slows it down but .. i cbf, tis easy to keep more variables //the point of this is to make it easier to code for now if(max > 0){ return -99999; } int cSum = 0; for(int i = start; i <= end; i++){ cSum += nums[i]; } return cSum; } @Override public String toString(){ return "Start " + start + " End " + end + " Sum : " + sum(); } }}