Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public static class largestSubsequence
- {
- public static maxSubsequence(int[] arr, int start, int end)
- {
- if(start == end)
- {
- return new obj(arr, start, end);
- }
- int pivot = (end-start)/2;
- obj left = maxSubsequence(arr, start, pivot);
- obj right = maxSubsequence(arr, pivot+1, end);
- obj result = new obj();
- int leftBorder; int leftBorderMax; int lIndex;
- for(int il = pivot; il >= 0; il--)
- {
- leftBorder += arr[il];
- if(leftBorderMax < leftBorder)
- {
- leftBorderMax = leftBorder;
- lIndex = il;
- }
- }
- int rightBorder; int rightBorderMax; int rIndex;
- for(int ir = pivot+1; ir <= end; ir++)
- {
- rightBorder+=arr[ir];
- if(rightBorderMax < rightBorder)
- {
- rightBorderMax = rightBorder;
- rIndex = ir;
- }
- }
- if(leftBorderMax > 0)
- {
- result.left = lIndex;
- }
- if(rightBorderMax > 0)
- {
- result.right = rIndex;
- }
- return max(left, right, result);
- }
- public static obj max(obj a, obj b, obj c)
- {
- }
- }
- public static class obj
- {
- public int left;
- public int right;
- public obj(){}
- public obj(int _left, int _right, int _index)
- {
- left = _left;
- right= _right;
- index= _index;
- }
- public static int getValue(int[] arr)
- {
- int result = 0;
- for(int i = left; i <= right; i++)
- {
- result += arr[i];
- }
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement