Maximum sum sub-array

Here is a slightly more complicated one:

Q. Given an integer array containing N positive and negative numbers, find the sub-array having the largest sum in linear time O(N) using constant space O(1).

Want some hint?

 You need to keep track of both the maximum sum so far and the maximum sum for including an element. 

My solution (in Java):

    int[] largestSum(int... a) {
        int start = 0, end = -1, curstart = 0, last = 0, sum = Integer.MIN_VALUE;

        for (int i = 0;i < a.length; i++) {
            last += a[i];
            sum = Math.max(last, sum);

            if (sum == last) {
                start = curstart;
                end = i;
            }
            if (last < 0) {
                last = 0;
                curstart = i + 1;
            }
        }
        return Arrays.copyOfRange(a, start, end + 1);
    }

Multiplies all except itself

That’s another simple algorithmic challenge.

Q. Given an array of integers A of size N > 1, produce an output array B of size N with B[i] = A[1]*A[2]…*A[i – 1]*A[i + 1]…*A[N], that is multiplies all elements in A except A[i] itself. Do it in linear time O(N) without using division.

Please think about it first before looking at my answer and I hope there is a better one than mine.

My solution (written in Java):

void mul(int[] a, int[] b) {
    // Compute b[i] = a[0]a[1]...a[i]
    b[0] = a[0];
    for (int i = 1; i < a.length; i++) {
        b[i] = b[i - 1] * a[i];
    }
    // Compute result, with v = a[n - 1]a[n - 2]...a[i] after loop i
    int v = 1;
    for (int i = a.length - 1; i > 0; i--) {
        b[i] = b[i - 1] * v;
        v *= a[i];
    }
    b[0] = v;
}

Detect duplicates

Trying to start a new category to archive some algorithmic problems that I come across. Let’s start with a very simple one.

Q. Given an array of N elements in which each element is an integer between 1 and N, detect if there are any duplicates in linear time O(n) and constant space O(1).

Please think about it being looking at my code.

My solution (in Java):

// If we are allowed to modify the array, it can be as simple as the following.
boolean detectDup(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int d = Math.abs(a[i]) - 1;
        if (a[d] < 0) {
            return true;
        }
        a[d] = -a[d];
    }
    return false;
}