动态规划子数组系列(二) 环形子数组的最大和

 题目：

  

---

解析： 

---

代码：    

public int maxSubarraySumCircular(int[] nums) {
        int sum = 0;

        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];

        int ret = 0, fmax = -0x3f3f3f3f, gmin = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            int x = nums[i-1];
            f[i] = Math.max(x,f[i-1] + x);
            fmax = Math.max(fmax,f[i]);

            g[i] = Math.min(x,g[i-1]+ x);
            gmin = Math.min(gmin,g[i]);
            sum += x;
        }

        return sum == gmin ? fmax : Math.max(fmax,sum-gmin);
    }

原文地址：https://blog.csdn.net/robin_suli/article/details/143824070

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！