一次翻转后的最大绿红之差

Given a char array that contains only 'R' and 'G'( Green and Red colors). You can pick a range and flip the colors in that range. (R->G, G->R). But you can only perform one operation of flipping and this flipping need to flip every element in your selected range. Find the maximum of number of G - number of R you can get。
想像这是一组红绿色彩的牌子，你现在开始翻牌子。你只能翻转一次，但一次可以把相邻的任何一组牌子一起翻转。问最大翻转后的绿红色之差。

首先这可以转换成一个 0,1数组的问题。
再详细点，我prefer转换成一个 -1, 1数组的问题而不是 0 和 1。
求的是一次翻转后数组能得到的最大和。
思路就是先算出当前的和，再找出和最小的subarray，把这个subarray翻转就好了。
所以问题就转换为一个求最小subarray sum的问题。
如果你把这个array转换成prefix sum的array, 对于每个点来说，以它结尾的subarray的最小值就等于prefixSum[i] - max(prefixSum[j] for j = 0 to i - 1);
(转换成prefix sum之后， 这就是一道买卖股票I的问题).
这样O(N)复杂度就可以解决。
代码见下。

public class May4 {
    public int maxAfterFlip(String str) {
        //input is GR string,
        // find the max of G - R after one flip;
        int N = str.length();
        int[] array = new int[N];
        for (int i = 0; i < N; i++) {
            array[i] = str.charAt(i) == 'G' ? 1 : -1;
        }
        int[] prefixSum = new int[N];
        for (int i = 0; i < N; i++) {
            prefixSum[i] = array[i] + (i > 0 ? prefixSum[i - 1] : 0);
        }
        int curSum = prefixSum[N - 1];
        //for any possible subarray, find the min value among these subarrays;
        int min = 0; // assume i can do 0 flip. need to confirm with interviewer
        int maxValue = 0; // a variable to keep record the maximum value seen from 0 till now
        for (int n : prefixSum) {
            min = Math.min(min, n - maxValue); // update the minValue 
            maxValue = Math.max(maxValue, n); // update previous maxValue;
        }
        return curSum - 2 * min; // flip the min;
    }
    public static void main(String[] args) {
        String str = "RGRGGG";
        May4 solultion = new May4();
        System.out.println(solultion.maxAfterFlip(str));
    }
}