Find the largest sum in an Array Problem

You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.

EXAMPLE

input: {2, -8, 3, -2, 4, -10}
output: 5 [ eg, {3, -2, 4} ]

Answer  :


You might have identified that dynamic programming is appropriate for this problem. Let’s write down the recurrence:

sum(i,j) = max_k sum(i,k) + sum(k+1, j)

This will give an O(N^3) solution. A brute force summing of the sequences will give the same time.

A simple linear algorithm will work by keep track of the current subsequence sum. If that sum ever drops below zero, that subsequence will not contribute to the subsequent maximal subsequence since it would reduce it by adding the negative sum.

public class SumArr {

    public static void main(String[] args) {
        int a[] = {6,-8, 3, -2, 4};
        int maxsum = 0;
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
        sum += a[i];
        if (maxsum < sum) {
        maxsum = sum;
        } else if (sum < 0) {
        sum = 0;
        }
        }
        System.out.println(maxsum);
    }
}

Read More

Java Problem Set 2

Write a function which calculates the sum of even Fibonacci numbers.

public static void main(String args[]) {
    for(int i=1;i<22;i++)
        System.out.print(sumofEvenFibonacci(i) + " ");
}

public static long sumofEvenFibonacci(int n) {
    // add your code here.
    return sum;
}

prints

0 0 2 2 2 10 10 10 44 44 44 188 188 188 798 798 798 3382 3382 3382 14328

Read More

Problem Set 3

The below questions are very interesting and amazing questions. So please do try it.

QUESTION 1

int a=5,*b=&a;
printf("%d",a**b);

Read More

Problem Set Java

 Predict the Output  


 Question 1

class Base {
    public void Print() {
        System.out.println("Base");
    }
}
class Derived extends Base {
    public void Print() {
        System.out.println("Derived");
    }
}
class Main{
    public static void DoPrint( Base o ) {
        o.Print();
    }
    public static void main(String[] args) {
        Base x = new Base();
        Base y = new Derived();
        Derived z = new Derived();
        DoPrint(x);
        DoPrint(y);
        DoPrint(z);
    }
}

Read More

Problem No.1

The below program is hideously slow. CAN YOU SPOT THE REASON?

public static void main(String args[]){
      Long sum=0L;
      for ( long i=0; i < Integer.MAX_VALUE; i++){
          sum += i;
      }
      System.out.println(sum);
}

Read More

Codeforces #47, Problem E

1:  import java.io.BufferedReader;  
2:  import java.io.IOException;  
3:  import java.io.InputStreamReader;  
4:  import java.util.HashMap;  
5:  public class Main {  
6:       public static void main(String[] args) throws IOException {  
7:            BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));  
8:            String ans=bf.readLine();  
9:            String var[]=ans.split(" ");  
10:            HashMap<Integer, Double> val=new HashMap<Integer, Double>();  
11:            double dx=0;  
12:            int cnt=0;  
13:            double rt1=0;  
14:            double rt2=0;  
15:            val.put(null, (double)1);  
16:            val.put(null, (double) 2);  
17:            for(double i=1;i<=Integer.parseInt(var[0]);i++){  
18:                 for(double j=1;j<=Integer.parseInt(var[1]);j++){  
19:                      dx= Math.pow(2*i, 2)-(4*j);  
20:                      if(dx>0){  
21:                           rt1= (((-2*i)+ Math.sqrt(dx)))/2;  
22:                           rt2= (((-2*i) - Math.sqrt(dx)))/2;  
23:                           if(val.get(cnt)==null){  
24:                                cnt=cnt+1;  
25:                                val.put(cnt,(double)rt2);  
26:                           }  
27:                           if(val.get(cnt)==null){  
28:                                cnt=cnt+1;  
29:                                val.put(cnt,(double)rt1);  
30:                           }  
31:                           if(val.containsValue(rt1) &&val.containsValue(rt2)){  
32:                           }else if(val.containsValue(rt1)){  
33:                                cnt=cnt+1;  
34:                                val.put(cnt,(double)rt2);  
35:                           }else if(val.containsValue(rt2)){  
36:                                cnt=cnt+1;  
37:                                val.put(cnt,(double)rt1);  
38:                           }else{  
39:                                cnt=cnt+2;  
40:                           val.put(cnt,(double)rt1);  
41:                           val.put(cnt,(double)rt2);  
42:                           }  
43:                      }else if(dx==0){  
44:                           rt1=(double) ((-2*i)/2);  
45:                           if(val.get(1)==null){  
46:                                cnt=cnt+1;  
47:                                val.put(cnt,(double) rt1);       
48:                           }  
49:                           if(val.containsValue(rt1)){   
50:                           }else{  
51:                                cnt=cnt+1;  
52:                                val.put(cnt,(double)rt1);  
53:                           }  
54:                      }  
55:                 }  
56:            }  
57:            System.out.println(cnt);  
58:       }  
59:  }  

Read More