Huawei Interview Question
SDE1sCountry: United States
Interview Type: In-Person
using dp approach
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
TreeMap<Integer,Integer> tmap=new TreeMap<Integer,Integer>();
void calSum(int b,int e,int a[]){
int tempSum=0;
for(int i=b;i<=e;i++){
tempSum=tempSum+a[i];
}
tmap.put(tempSum,tempSum);
}
int function(int beg,int end ,int arr[]){
if(beg<=end){
calSum(beg,end,arr);
function(beg+1,end-1,arr);
function(beg+1,end,arr);
function(beg,end-1,arr);}
else{
return 0;
}
return 0;
}
void seeResult(){
System.out.println(tmap.lastKey().toString());
}
public static void main (String[] args) throws java.lang.Exception
{
int array[]={-2,1,-3,4,-1,2,1,-5,4};
Ideone id=new Ideone();
id.function(0,array.length-1,array);
id.seeResult();
}
}
Kadane's algorithm
- Gear February 17, 2017