Skip to content

Instantly share code, notes, and snippets.

@thmain
Last active May 26, 2018 23:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save thmain/cd431ea9990d40d02c40 to your computer and use it in GitHub Desktop.
Save thmain/cd431ea9990d40d02c40 to your computer and use it in GitHub Desktop.
import java.util.Arrays;
public class MaximumSubArrayDP {
//bottom up approach
public int solve(int [] a){
int [] solution = new int[a.length+1];
solution[0] = 0;
for (int j = 1; j <solution.length ; j++) {
solution[j] = Math.max(solution[j-1]+a[j-1],a[j-1]);
}
//this will print the solution matrix
//System.out.println(Arrays.toString(solution));
//now return the maximum in the solution arrayyy
int result = solution[0];
for (int j = 1; j <solution.length ; j++) {
if(result<solution[j])
result = solution[j];
}
return result;
}
public static void main(String[] args) {
int arrA[] = { 1, 2, -3, -4, 2, 7, -2, 3 };
MaximumSubArrayDP i = new MaximumSubArrayDP();
System.out.println("Maximum subarray is " + i.solve(arrA));
}
}
@jamerson
Copy link

jamerson commented Jan 6, 2017

There is a syntax error on line 11, missing a ] at the end:
solution[j] = Math.max(solution[j-1]+a[j-1],a[j-1]);

@thmain
Copy link
Author

thmain commented May 26, 2018

corrected it, thanks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment