Kiran T
BAN USERThe problem statement says left inclusive and right inclusive.
The example works with zero indexed too.
Another note, the array goes back to normal after each query, so we can iterate array from 0->Li, Ri->Li, (Ri+1)->length.
It looks to be Kadane's algorithm with small modification.
import java.util.*;
public class Solution {
static int subArraySumWithFlip(int arr[], int l, int r) {
int max_so_far = Arrays.stream(arr).max().getAsInt();
int max_sum = max_so_far;
for (int i=0; i<l; i++) {
max_so_far = Math.max(arr[i], max_so_far + arr[i]);
max_sum = Math.max(max_sum, max_so_far);
}
for (int i=r; i>=l; i--) {
max_so_far = Math.max(arr[i], max_so_far + arr[i]);
max_sum = Math.max(max_sum, max_so_far);
}
for (int i=r+1; i<arr.length; i++) {
max_so_far = Math.max(arr[i], max_so_far + arr[i]);
max_sum = Math.max(max_sum, max_so_far);
}
return max_sum;
}
public static void main(String args[]){
int[] arr = new int[]{5,-5,-2,4,1};
System.out.println(subArraySumWithFlip(arr,0,2));
}
}
public class Node {
int low; int high; Node left; Node right;
Node(int low, int high) {
this.low = low;
this.high = high;
this.left=null;
this.right=null;
}
static Node insert(int low, int high, Node root) {
if (root == null)
return new Node(low, high);
// lies within root interval, do nothing
if (root.low <= low && root.high>=high)
return root;
// lies to right, no intersection
if (root.high <= low) {
root.left = insert(low, high, root.left);
return root;
}
// lies to left, no intersection
if (root.low >= high) {
root.right = insert(low, high, root.right);
return root;
}
// intersect with left boundary
if (root.low > low) {
root.left = insert(low, root.low, root.left);
}
// intersect with right boundary
if (root.high < high) {
root.right = insert(root.high, high, root.right);
}
return root;
}
static int count(Node root) {
if (root == null) return 0;
return root.high - root.low + count(root.left) + count(root.right);
}
public static void main(String args[]){
Node root = null;
root = insert(1,4, root);
root = insert(2,10, root);
root = insert(1,7, root);
System.out.println(count(root));
}
}
- Kiran T October 28, 2019