CareerCup

// Another version
// Lease cars
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

struct TIME_t {
    TIME_t(int hh, int mm, int c):h(hh), m(mm), cars(c){}
    int h;
    int m;
    int cars;  // +ve => cars used; -ve => cars given back
};

typedef struct TIME_t TIME;

bool operator<(const TIME& t1, const TIME& t2){
    if(t1.h != t2.h) return t1.h < t2.h;
    return t1.m < t2.m;
}

bool operator==(const TIME& t1, const TIME& t2){
    if(t1.h != t2.h) return false;
    if(t1.m != t2.m) return false;
    return true;
}

int main() {
    freopen("LeaseCarsInput.txt", "r", stdin);
    vector<TIME> times;
    int startH, endH, cars;
    while(scanf("%d", &startH), startH != -1){
        scanf("%d", &endH);
        scanf("%d", &cars);
        if(endH<startH){
            cout << "Wrong Input";
            return 0;
        }
        
        times.push_back(TIME(startH,0,cars));
        times.push_back(TIME(endH,0,-cars));
    }
    if(!times.size()) return 0;

    std::sort(times.begin(), times.end());
    
    int totalCars=0;
    int availableCars=0;
    for(int i=0; i<times.size();){
        int carsNeededNow = times[i].cars;
        i++;
        while(i<times.size() && times[i]==times[i-1]){
            carsNeededNow += times[i].cars;
            i++;
        }

        if(carsNeededNow <= availableCars){
            availableCars -= carsNeededNow;
        } else {
            totalCars += carsNeededNow - availableCars;
        }
    }
 
    cout << "Total Cars: " << totalCars << endl;    
    return 0;
}

// Test case
//Format: start_time    end_time    cars
// -1 => exit  
1   3   2
2   3   3
3   4   4
5   6   2
-1

// Lay off engine for Ace Shippping Corp
// Strategy: Use multiway tree to store organization hierarchy
// Also use a map to keep track of all nodes of the tree for
// easy access.
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

class Employee {
    public:
        typedef enum{
            Manager,
            IC // Individual Contributor
        }Role;
        
        Employee(int id, string name, int mgr_id, int rating, double salary, Role role=IC) {
            this->id = id;
            this->name = name;
            this->mgr_id = mgr_id;
            this->rating = rating;
            this->salary = salary;
        }
        
        bool addDirectReports(Employee* emp) {
            if(role != Manager) {
                cout << "Can't add direct reports as role is not Manager\n";
                return false;
            }
            
            directReports.push_back(emp);           
            return true;
        }

        bool removeDirectReports(Employee* emp) {
            // TODO
            return true;
        }
                
        int id;
        int mgr_id;
        string name;
        int rating;
        double salary;
        Role role;
        vector<Employee*> directReports;
};

bool CMP(Employee* e1, Employee* e2){
    if(e1->rating != e2->rating) return e1->rating < e2->rating; // prioritize lesser rating
    return e1->salary > e2->salary; // prioritize more salary if rating is same
}

int ComputeSavings(Employee* root, int k){
    if(!root) {
        return 0;
    }
    
    if(root->role == Employee::IC) return 0;
    
    int savings=0;

    std::sort(root->directReports.begin(), root->directReports.end(), CMP);    
    for(int i=0; i<root->directReports.size() && i<k; i++)
        savings += root->directReports[i]->salary;
    
    for(int i=0; i<root->directReports.size(); i++)
        savings += ComputeSavings(root->directReports[i], k);
    
    return savings;
}

int main() {
    map<int, Employee*> empMap;
    freopen("input.txt", "r", stdin);
    
    // Read inputs
    // Exit if id = 0
    int id;
    while(scanf("%d", &id), id) {
        char name[100];
        scanf("%s", name);
        int mgr_id;
        scanf("%d", &mgr_id);
        int salary;
        scanf("%d", &salary);
        int rating;
        scanf("%d", &rating);
        
        Employee* emp = new Employee(id,string(name),mgr_id,rating,salary);
        empMap[id]=emp;
    }
    
    // Fix role and add direct reports for managers
    for(map<int, Employee*>::iterator it = empMap.begin(); it != empMap.end(); ++it){
        if((it->second)->mgr_id != -1) {
            empMap[(it->second)->mgr_id]->role = Employee::Manager;
            empMap[(it->second)->mgr_id]->addDirectReports(it->second);
        }
    }
    
    cout << "Savings: " << ComputeSavings(empMap[2], 1) << endl;
    
    // Free memory
    for(map<int, Employee*>::iterator it = empMap.begin(); it != empMap.end(); ++it){
        Employee* emp = it->second;
        delete emp;
    }
    
    return 0;
}

// Test case
// Format: Emp_id name manager_id salary rating
1   ROOT   -1  -1   -1
2   CEO   1   100    5
3   VP1   2   10     3
4   VP2   2   20     2
5   A1   3   5      3
6   A2   3   6      3
7   B1   4   5      4
8   B2   4   8      2
0

/* Adopted from Rob Pike's implementation  */
#include <iostream>
#include <stdio.h>

using namespace std;

bool RegExMatchHelper(char* regex, char* text);

bool RegExMatchKleeneStar (char c, char* regex, char* text){
    do {
        if(RegExMatchHelper(regex, text)) return true;
    } while (*text != '\0' && (*text++ == c || c == '.'));
    
    return false;
}

bool RegExMatchHelper(char* regex, char* text){
    if(regex[0] == '\0') return true;
    if(regex[0] == '$' && regex[1] == '\0') return *text == '\0';
    if(regex[1] == '*') {
        return RegExMatchKleeneStar(regex[0], regex+2, text);
    } 
    if(*text != '\0' && (*text++ == regex[0] || regex[0] == '.')) {
            return RegExMatchHelper(regex+1, text);
    }
    
    return false;
}

bool RegExMatcher (char* regex, char* text){
    if(regex[0] == '\0') return true;
    
    if(regex[0] == '^') {
        return RegExMatchHelper(regex+1, text);
    } else {
        do {
            if(RegExMatchHelper(regex, text)) return true;
        } while (*text++ != '\0');
    }
    
    return false;
}

int main(int argc, char** argv) {
    if(argc != 3) cout << "Wrong format\n";
    if(RegExMatcher(argv[1],argv[2])) cout << "Match\n";
    else cout << "Doesn't match\n";
    return 0;
}

//Car delivery
//Strategy:
//1. Prepare two lists of orders. One sorted by start time and
//   another sorted by end time
//2. Iterate two list simultaneously
//3. If we encounter smaller start time, we increment # of cars
//4. If we encounter smaller end time, we decrement # of cars
//5. Take care of junctions where start and end time matches
//6. Keep track of maximum # of cars encountered so far
// Input:
//1 3 2
//2 3 3
//3 4 4
//5 6 2
//0 0 0-> exit
// Time complexity = time to sort the list [2*nlog(n)] + main computation loop (n) = O(nlogn)
// Space complexity = O(n)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct Order_t {
    Order_t(int s, int e, int n):start(s),end(e),nCars(n){}
    int start;
    int end;
    int nCars; // # of cars
};
typedef struct Order_t Order;

bool Comp1(Order a, Order b){
    return a.start < b.start;
}

bool Comp2(Order a, Order b){
    return a.end < b.end;
}

int main(){
    
    freopen("input.txt", "r", stdin);
    vector<Order> l1,l2;
    while(true){
        int start,end,n;
        scanf("%d", &start);
        scanf("%d", &end);
        scanf("%d", &n);
        
        if(start == 0) break;
        
        l1.push_back(Order(start,end,n));
        l2.push_back(Order(start,end,n));
    }
    
    sort(l1.begin(), l1.end(), Comp1); // sort by start time
    sort(l2.begin(), l2.end(), Comp2); // sort by end time
    
    int max_cars=0,n_cars=0;
    
    for(int i=0,j=0; i<l1.size() && j<l2.size(); ){
        if(l1[i].start < l2[j].end) {
            n_cars += l1[i].nCars; // Increase number of cars
            i++;
        } else if (l1[i].start > l2[j].end) {
            n_cars -= l2[j].nCars; // Decrease number of cars
            j++;
        } else { // l1[i].start == l2[j].end
            int time = l1[i].start;
            n_cars += l1[i].nCars;
            n_cars -= l2[j].nCars;
            i++;
            j++;
            if((i<l1.size() && l1[i].start == time) ||
               (j <l2.size() && l2[j].end == time)) continue;   
                        // We want to continue before adjusting max_cars
                        // since we want to consider all start and end points
                        // at a particular time
        }
        if(max_cars < n_cars) max_cars = n_cars; // Compute max cars
    }

    if(max_cars < n_cars) max_cars = n_cars; // re-compute max_cars if we missed last iteration
                                             // of the above loop

    cout << "Result: " << max_cars << endl;
    
    return 0;
}

//Car delivery
//Strategy:
//1. Prepare two lists of orders. One sorted by start time and
//   another sorted by end time
//2. Iterate two list simultaneously
//3. If we encounter smaller start time, we increment # of cars
//4. If we encounter smaller end time, we decrement # of cars
//5. Take care of junctions where start and end time matches
//6. Keep track of maximum # of cars encountered so far
// Input:
//1 3 2
//2 3 3
//3 4 4
//5 6 2
//0 0 0-> exit
// Time complexity = time to sort the list [2*nlog(n)] + main computation loop (n) = O(nlogn)
// Space complexity = O(n)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct Order_t {
    Order_t(int s, int e, int n):start(s),end(e),nCars(n){}
    int start;
    int end;
    int nCars; // # of cars
};
typedef struct Order_t Order;

bool Comp1(Order a, Order b){
    return a.start < b.start;
}

bool Comp2(Order a, Order b){
    return a.end < b.end;
}

int main(){
    
    freopen("input.txt", "r", stdin);
    vector<Order> l1,l2;
    while(true){
        int start,end,n;
        scanf("%d", &start);
        scanf("%d", &end);
        scanf("%d", &n);
        
        if(start == 0) break;
        
        l1.push_back(Order(start,end,n));
        l2.push_back(Order(start,end,n));
    }
    
    sort(l1.begin(), l1.end(), Comp1); // sort by start time
    sort(l2.begin(), l2.end(), Comp2); // sort by end time
    
    int max_cars=0,n_cars=0;
    
    for(int i=0,j=0; i<l1.size() && j<l2.size(); ){
        if(l1[i].start < l2[j].end) {
            n_cars += l1[i].nCars; // Increase number of cars
            i++;
        } else if (l1[i].start > l2[j].end) {
            n_cars -= l2[j].nCars; // Decrease number of cars
            j++;
        } else { // l1[i].start == l2[j].end
            int time = l1[i].start;
            n_cars += l1[i].nCars;
            n_cars -= l2[j].nCars;
            i++;
            j++;
            if((i<l1.size() && l1[i].start == time) ||
               (j <l2.size() && l2[j].end == time)) continue;   
                        // We want to continue before adjusting max_cars
                        // since we want to consider all start and end points
                        // at a particular time
        }
        if(max_cars < n_cars) max_cars = n_cars; // Compute max cars
    }

    if(max_cars < n_cars) max_cars = n_cars; // re-compute max_cars if we missed last iteration
                                             // of the above loop

    cout << "Result: " << max_cars << endl;
    
    return 0;
}

/*
Strategy: From LSB to MSB, identify first consecutive bits
those are different and swap/flip them.
No solution for 0x0 and 0xffffffffffffffff
*/
#include <iostream>
#include <stdio.h>

using namespace std;

int main(){
    unsigned long long x;
    scanf("%lld", &x);
    
    if(x == 0 || x == 0xffffffffffffffff) {
        cout << "No solution\n";
        return 0;
    }
    
    unsigned long long x_tmp = x;
    int i=0;
    int prevBit = x_tmp & 0x1;
    while(x_tmp){
        x_tmp >>= 1;
        if(prevBit != (x_tmp&0x1)) break;
        prevBit = x_tmp & 0x1;
        i++;
    }
    
    unsigned long long y = x ^ (3<<i);
    cout << y << endl;
    
    return 0;
}

/*
Sample input
4
1 2 4 3
3 2 1 4
*/
#include <iostream>
#include <stdio.h>

using namespace std;

void Convert(int* a, int* b, int N){
    int* m_a = new int[N+1];
    
    for(int i=0; i<N; i++) {
        m_a[a[i]] = i;
    }
    
    for(int i=0; i<N; i++){
        if(a[i] == b[i]) continue;
        
        int j = m_a[b[i]];
        printf("Swap %dth %d with %dth %d\n", i, a[i], j, a[j]);
        int tmp = a[j];
        a[j] = a[i];
        a[i] = tmp;
        m_a[a[j]] = j;
    }
    
    delete [] m_a;
}

int main() {
    freopen("input.txt", "r", stdin);
    int N;
    scanf("%d", &N);
    int* a = new int[N];
    int* b = new int[N];
    
    for(int i=0; i<N; i++) scanf("%d", &a[i]);
    for(int i=0; i<N; i++) scanf("%d", &b[i]);
    
    Convert(a, b, N);
    
    delete [] a;
    delete [] b;
    return 0;
}

/*
A C++ solution using map.
We store the courses in a map and schedule using greedy strategy.
We also put the courses in separate vectors for easy access.

In case there are more courses in a semester than allowed, we give
higher precedence to 'Fall' and 'Spring' than 'Both', since 'Both' can be
taken in any iteration. 
*/

#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <string>

using namespace std;
#define BIG_INT 999999
enum semester{
    Fall,
    Spring,
    Both
};

struct course;
typedef struct course Course;

struct course{
    string name;
    semester s;
    int doneAt;
    std::vector<string> dep;
};

typedef std::map<string, Course*> CourseMap;

int CalculateSemester(CourseMap& cmap,vector<string>* courses, int m){
    int count = 0;
    
    while(!courses[Fall].empty() || !courses[Spring].empty() || !courses[Both].empty()){
        int size = 0;
        
        int s = count%2;
        // Schedule courses for Fall or Spring
        while(!courses[s].empty() && size < m){
            bool added = false;
            for(int i=0; i<courses[s].size() && size < m; i++){
                if(cmap[courses[s][i]]->doneAt == BIG_INT){
                    bool include = true;
                    int j=0;
                    for(j=0; j<cmap[courses[s][i]]->dep.size(); j++){
                        if(cmap[cmap[courses[s][i]]->dep[j]]->doneAt >= count){
                            include=false;
                            break;
                        }
                    }
                    if(include && size < m){
                        cmap[courses[s][i]]->doneAt = count;
                        size++;
                        courses[s].erase(courses[s].begin()+i);
                        added = true;
                    }
                }
            }
            if(!added) break;
        }

        // Schedule coursed from Both
        while(!courses[2].empty() && size < m){
            bool added = false;
            for(int i=0; i<courses[2].size() && size < m; i++){
                if(cmap[courses[2][i]]->doneAt == BIG_INT){
                    bool include = true;
                    int j=0;
                    for(j=0; j<cmap[courses[2][i]]->dep.size(); j++){
                        if(cmap[cmap[courses[2][i]]->dep[j]]->doneAt >= count){
                            include=false;
                            break;
                        }
                    }
                    if(include && size < m){
                        cmap[courses[2][i]]->doneAt = count;
                        size++;
                        courses[2].erase(courses[2].begin()+i);
                        added = true;
                    }
                }
            }
            if(!added) break;
        }
        
        count++;        
    }
    
    return count;
}

int main() {
    freopen("input.txt", "r", stdin);
    while(true){
        int n;
        scanf("%d", &n);
        if(n == -1) break;
        int m;
        scanf("%d", &m);
        if(m == -1) break;
        
        CourseMap cmap;
        vector<string> courses[3];
        char buf[100];
        for(int i=0; i<n; i++) scanf("%s", buf);
        for(int i=0; i<n; i++){
            scanf("%s", buf);
            Course* c = new Course();
            c->doneAt = BIG_INT; // some big number
            c->name = string(buf);
            scanf("%s", buf);
            c->s = (buf[0] == 'F' ? Fall : (buf[0] == 'S' ? Spring : Both));
            courses[c->s].push_back(c->name);
            int dp;
            scanf("%d", &dp);
            for(int j=0; j<dp; j++){
                scanf("%s", buf);
                c->dep.push_back(string(buf));
            }
            cmap[c->name] = c;
        }

        cout << "The minimum number of semesters required to graduate is " << CalculateSemester(cmap,&courses[0],m) << endl;
    }
    
    return 0;
}

/*
A complete pow(x,y) implementation supporting fraction powers as well.
*/
#include <iostream>
#include <stdio.h>

using namespace std;

typedef unsigned long long UINT64;

int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

double powI(double x, int n){
    if(x==0 && n) return 0;
    if(n==0) return 1;
    
    double powTable[100];
    powTable[0] = 1;
    powTable[1] = x;
    for(int i=2; i<=n;i++) powTable[i] = 0;

    int i=1;
    double result = 1;
    while(i<n){
        if(2*i <= n){
            if(!powTable[2*i]) powTable[2*i] = powTable[i] * powTable[i];
            result = powTable[2*i];
            i *= 2;
            continue;
        }
        
        int j = n - i;
        while(!powTable[j]) j--;
        result *= powTable[j];
        i = i+j;
    }
    
    return result;
}

void ExtractFraction(double P, int& m, int& n){
    int x=1;
    while(P != (int)P){
        P *= 10;
        x *= 10;
    }
    
    int d=gcd(P, x);
    m=P/d;
    n=x/d;
}

// Using  Newton–Raphson method
double CalculateNRoot(int x, int n) {
    double y=1;
    double delta = 1;
    
    while(true){
        double yn = powI(y,n);
        double FX = yn-x;
        double FDX = n*(yn/y);
        double m = y - FX/FDX;
        delta = (m>y)? (m-y) : (y-m);
        y=m;
        if(delta < .000000001) break;
    }

    return y;
}

// calculate x^y
double pow(double x, double y){
    if(x<0) return -1; // -ve x not supported
    if(x==0 && y==0) return -1;
    if(x==0) return 0;
    if(y==0) return 1;
    
    double Y = y>=0 ? y : -y;
    double result=0;
    if(Y == (int)Y){  // Y is an integer
        result = powI(x,Y);
    } else { // fraction Y
        int m,n;
        ExtractFraction(Y, m, n);
        result = powI(x, m);
        result = CalculateNRoot(result, n);
    }
    
    return y>=0 ? result : (1/result);
}

int main() {
    cout << pow(2, 16) << endl;
    cout << pow(2, -16) << endl;
    cout << pow(2, 1.6) << endl;
    return 0;
}

/*
This is a generalized problem for next higher permutation.
If A and B have same digits, this it is the special case of
next higher permutation problem.

Strategy:
---------
1. Count all digits of A in a Hash (mA),
we need these digits to create new number.
2. Try matching B digits with A-map(mA) from MSB->towards->LSB, because
we want next higher permutation. Therefore we want to keep MSB digits
as much same as possible.
3. While doing this, we can have two cases.
3a. case#1: At index i, B differs from A. Then try to get a digit from
            mA which is just greater than B[i]. If found, place it in C[i]
            if not found, we have to go left until i==0
3b. case#2: We have exhausted B and A. This means, A and B are permutations.
            In this case also, we have to go left.
4. The only difference between case1 and 2 is, in case#1, [0,i-1] digits of
   A and B are same but i differs, but for case#2, [0,i] digits are same. We need
   to know this because, while left tracking, we need to give back digits to mA as necessary.
5. If (3) terminates at some i>=0, then copy B[0..i-1] => C[0...i-1]
6. Copy rest of digits from mA to C[i+1....N-1] in increasing order.
7. If i=-1, then no solution.

Complexity = O(n) [n = number of digits]
*/

#include <iostream>
#include <stdio.h>

using namespace std;

#define D_(c) ((int)c-(int)'0')
#define C_(i) ((char)(i+(int)'0'))

int main() {
    freopen("input.txt", "r", stdin);
    char A[100],B[100],C[100],mA[10];
    scanf("%s", A);
    scanf("%s", B);
    
    for(int i=0; i<10; i++) mA[i] = 0;

    int sA=0;
    while(A[sA] != '\0' && A[sA] != '\n') {
        mA[D_(A[sA])]++;
        sA++;
    }
    int sB=0;
    while(B[sB] != '\0' && B[sB] != '\n') sB++;

    if(sA != sB) {
        cout << "A & B size mismatch. No solution!!.\n";
        return 0;
    }
    int N = sA;
    
    int i=0;
    bool match;
    for(i=0; i<N; i++){
        match = false;
        if(mA[D_(B[i])]) {
            match=true;
            mA[D_(B[i])]--;
            continue;
        }
        break;
    }
    
    if(i==N) i--;

    while(i>=0){
        int j;
        for(j=D_(B[i])+1; j<10; j++) {
            if(mA[j]) {
                if(match) mA[D_(B[i])]++;
                C[i] = C_(j);
                mA[j]--;
                break;
            }
        }
        if(j == 10) {
            if(match) mA[D_(B[i])]++;
            i--;
            match=true;
            continue;
        }
        
        for(int k=0; k<i; k++) C[k] = B[k];
        int p=9;
        for(int k=N-1; k>i; k--) {
            while(mA[p]==0)p--;
            C[k]=C_(p);
            mA[p]--;
        }
        break;
    }
    
    if(i<0) {
        cout << "No solution\n";
        return 0;
    }
    
    C[N] = '\0';
    cout << C;
    
    return 0;
}

A solution using bit-wise operator.
Complexity for isOn(i) => O(1)
Complexity for toggle => O(n/32) for n<32, it is O(1)

If we use 64 bit integer, it will be O(n/64)

The assumption is, we take each integer bit-wise operation as one machine instruction.
i.e. (i<<32) is actually one machine instruction.

#include <iostream>
#include <stdio.h>

using namespace std;

typedef unsigned int UINT32;

class Bulbs {
    public:
        Bulbs(int n);
        bool isOn(int i);
        void toggle(int start, int end);
    
    private:
        int val;
        int n;
        int L;
        UINT32 s[200];
};

Bulbs::Bulbs(int val) {
    L = sizeof(UINT32);
    this->val = val;
    n = val/L + val%L ? 1 : 0;
    for(int i=0; i<n; i++) s[i] = 0;
}

bool Bulbs::isOn(int i) {
    int b = i / L;
    int off = i % L;
    return (s[b] & (1<<off)) ? true : false;
}

void Bulbs::toggle(int start, int end) {
    int sb = start / L;
    int so = start % L;
    int eb = end / L;
    int eo = end % L;
    int l = eb - sb + 1;
    
    if(sb == eb) {
        s[sb] = s[sb]^(((1 << l) - 1) << so);
        return;
    }
    
    for (int i=1; sb+i < eb; i++) {
        s[sb+i] = s[sb+i]^0xffffffff;
    }
    
    l = L - sb + 1;
    s[sb] = s[sb]^(((1 << l) - 1) << so);
    s[eb] = s[eb]^((1<<eo)-1);
}

int main() {
    Bulbs b(100);
    
    b.toggle(50, 60);
    
    cout << b.isOn(49) << endl;
    cout << b.isOn(55) << endl;
    cout << b.isOn(155) << endl;
    b.toggle(40, 200);
    cout << "*************************\n";    
    cout << b.isOn(49) << endl;
    cout << b.isOn(55) << endl;
    cout << b.isOn(155) << endl;
    cout << "*************************\n";
    b.toggle(40, 200);
    
    cout << b.isOn(49) << endl;
    cout << b.isOn(55) << endl;
    cout << b.isOn(155) << endl;
    cout << "*************************\n";
    return 0;
}

#include <iostream>
#include <stdio.h>

using namespace std;

int TestPlus(int** m, int x, int y, int span) {
    if(m[x][y] == 0) return 0;
    int count=0;
    for(int i=1; i<=span/2; i++) {
        if(m[x][y+i] == 1 && m[x][y-i] == 1 &&
           m[x+i][y] == 1 && m[x-i][y] == 1) {
               count++;
               continue;
           }
           break;
    }
    
    return (count == 0 ? count : 4*count+1);
}

int LargestPlus(int** m, int N) {
    int n = (N%2 == 0 ? N-1 : N);  
    int max = 0;
    for(int span = n; span >= 3; span -= 2) {
        if(max >= 2*span-1) return max;
        
        for(int x=span/2; x+span/2 < N; x++) {
            for(int y=span/2; y+span/2 < N; y++) {
                int val = TestPlus(m, x, y, span);
                if(max < val) max = val;
                if(max == 2*span-1) return max;
            }
        }
    }
    
    return max;
}

int main() {
    freopen("input.txt", "r", stdin);
    int N;
    scanf("%d", &N);
    int** m;
    m = new int*[N];
    for(int i=0; i<N; i++) m[i] = new int[N];
    
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++){
            scanf("%d", &m[i][j]); 
        }
    }
    cout << LargestPlus(m, N) << endl;
    
    for(int i=0; i<N; i++) delete [] m[i];
    delete [] m;
    return 0;
}

If you run linear loop for every pair of indexes, then you are no more with O(n^3) complexity.
It is exponential. The complexity will lead to Catalan number.

If we want to solve this problem with lower complexity, we need more attributes of the input
array which will help us in further optimization.

Sometimes, apparently O(n^3) sounds high, since we like to talk about O(n) or lg(n) but
unfortunately O(n^3) is optimal; you can't go further down.

For more details, refer matrix chain multiplication problem from CRLS book.

Also note that, O(n^3) is worst case asymptotic complexity.
In average case, the program will terminate much before than that.

However, I will love to see a faster algorithm; but for that we need more attributes
which I might have missed.

Algorithm
-------------

The problem provides couple of attributes to the input and output requirements which provide a hint towards the solution.

1. We need to find subarrays with maximum dot-product. Dot product or scalar product only accounts magnitude of vectors. For our case, it means that, we will only deal with absolute value of integers ignoring the sign.

2. We will deal with dot-product of sub-arrays of input string where we will have to compute product of sub-arrays repetitively. To optimize the dot-product computation of arrays, we will use dynamic programming (DP) and store the results in a 2-dimensional array for further processing.
We define array M[][] where M[i][j] stores dot-product for sub-array starting at index i and ending at index j.

If the input array is A[size], ∀ 0 ≤ i,j < size & i ≤ j

M[i][j] = A[i] for i = j
= M[i][j-1] . |A[j]| for i < j
= Invalid (-1) for i > j

3. Once we have calculated dot-product matrix, now it’s time to compute the intended sub-arrays.

a. Since we have array of integers, any array will have larger dot-product compared to its sub-arrays.
b. We need non-overlapping sub-arrays. The maximum non-overlapping sub-array length = size/2
Therefore, we start finding sub-arrays of length size/2 until 1. We will terminate our iteration once we find one based on property (a).

C++ Code
--------------
#include <iostream>
#include <stdlib.h>

using namespace std;

// Return true for success and false for failure
// In case of success, (s1,e1) is the start and end index of subArray-1
// and (s2,e2) is subarray-2
bool MaxDOTProduct(int* A, int size, int& s1, int& e1, int& s2, int& e2)
{
    
    bool found = false;
    
    // Prepare dot-product matrix
    int** M = new int*[size];
    for(int i=0; i<size; i++) {
        M[i] = new int[size];
        M[i][i] = abs(A[i]);
    }
    
    for (int span = 2; span <= size; span++){
        // i = start index and j = end index
        int i,j;
        for (j=span-1, i=j-span+1; j < size; i++, j++) {
            M[i][j] = M[i][j-1] * abs(A[j]);
        }
    }
    
    
    // Now find the sub-strings
    for (int length = size/2; length >= 1; length--) {
        for (e1=length-1, s1=e1-length+1; e1<size; s1++, e1++){
            for (s2=e1+1,e2=s2+length-1; e2 < size; s2++, e2++) {
                if (M[s1][e1] == M[s2][e2]) {
                    found = true;
                    break;
                }
            }
            
            if (found) break;
        }
        
        if (found) break;
    }
    
    
    // Clean dot-product matrix
    for (int i=0; i < size; i++)
        delete M[i];
    delete [] M;
    return found;
}

int main()
{
    int* A = new int[10];
    A[0] = 1; A[1] = 2; A[2] = 3; A[3]= 4; A[4] = -44; A[5] = 99; A[6] = 4; A[7] = 3; A[8] = 44; A[9] = 99;
    int s1,e1,s2,e2;
    if(MaxDOTProduct(A, 10, s1, e1, s2, e2))
    {
        cout << "s1=" << s1 << " e1=" << e1 << " s2=" << s2 << " e2=" << e2 << endl;
    } else {
        cout << "No result\n";
    }
    
    delete A;
}

Space & Time Complexity
-----------------------------------
We have taken O(n^2) additional space to store dot-product matrix.
The time complexity to prepare dot-matrix is O(n^2) since it is a DP solution.

Sub-string computation has three nested loops.
Outermost loop will iterate (n/2) times.
The two inner loops compare dot-products of all non-overlapping substrings for sub-string length (l).

Total number of comparisons for a particular length (l) is
C = (n-2l+1) + {(n-2l+1)-1} + {(n-2l+1)-2} + … + 2 + 1
i.e. C = (n-2l+1)(n-2l+2)/2 for l = n/2 to 1

Therefore asymptotic upper bound is O(n^3)
Hence Time complexity = O(n^2) + O(n^3) = O(n^3)

For more info refer: imdiba.blogspot.in